【Golang Theme learning Month 】 Brushing questions is much better than playing games. The sense of achievement is getting stronger and stronger. I insist on brushing one question every day, exercising 30 minutes every day, waiting for 8-block abs and waiting for big factory offer.

😄


  \color{red}{~}

I believe that if you encounter this problem in the interview, logical, correct expression, tear

There should be more than a few candidates.

Unfamiliar to the tree friend, can see the front of the basic training problem oh!

  • Sequential traversal in a binary tree – iteration, recursion

  • Binary tree before sequential traversal – iteration, recursion

  • Binary tree after sequential traversal – iteration, recursion

  • Sequence traversal of binary tree – iteration, recursion

  • Maximum depth of binary tree – iteration, recursion

  • Symmetric binary tree of binary tree – iteration, recursion

  • Binary tree path summation | Go theme month – iteration, recursion

  • Construct binary tree | Go theme month by traversing sequence from middle order to back order

  • Recent common ancestor of binary tree | Go theme month

  • Binary tree serialization and deserialization | Go topic month

  • Verify binary search tree | Go theme month

  • Binary search tree in search | Go subject month

  • Binary search tree insert operations | Go theme month

  • Delete node | Go subject month in binary search tree

Leecode 589. Antecedent traversal of N fork trees

Given an n-tree, returns a sequential traversal of its node values.

The n-fork tree is serialized in the input as a sequential traversal, with each set of child nodes separated by null values (see example).

 

Advanced:

Recursion is easy. Can you do it iteratively?

 

Example 1:

Input: root = [1,null,3,2,4,null,5,6]

Output:,3,5,6,2,4 [1]

Example 2:

Input: root = [1, null, 2, 5-tetrafluorobenzoic, null, null, 6, 7, null, 8, null, 9, 10, null, null, 11, null, 12, null, 13, null, null, 14]

Output:,2,3,6,7,11,14,4,8,12,5,9,13,10 [1]

Tip:

The height of an n-tree is less than or equal to 1000

The total number of nodes is in the range [0, 10^4]

Reference code

Each set of child nodes is separated by a null value

Each set of child nodes represents a root, a left node, or a right node. If we look at example 2, we should have no problems

DFS in GO

The same thing that we used for binary tree traversal, the same thing that we used here, exactly the same idea.

Stack is first in last out.

Anterior traversal: root, left, right

Obviously, if we push the root onto the stack, if there’s a left node, we’ll push it, if there’s no left node.

Because the last node added comes out first.

Same thing on the right-hand side.

Class Node {int val; List<Node> children; Node(int x, List<Node> children) { val = x; children = children; }}Copy the code
var res []int

func preorder(root *Node) []int {
	res = []int{}
	dfs(root)
	return res
}

func dfs(root *Node)  {
	ifroot ! = nil { res = append(res, root.Val)for _,n := range root.Children {
		    dfs(n)      
        }
	}
}




Copy the code

The iterative version

func preorder(root *Node) []int {
	var res []int
	var stack = []*Node{root}
	for 0 < len(stack) {
		forroot ! = nil { res = append(res, root.Val)// Preorder output
			if 0 == len(root.Children) {
				break
			}
			for i := len(root.Children) - 1; 0 < i; i-- {
				stack = append(stack, root.Children[i]) / / into the stack
			}
			root = root.Children[0]
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]}return res
}


Copy the code

JAVA

/ / iteration
class Solution {
    public List<Integer> preorder(Node root){
        List<Integer> list = new ArrayList<>();
        Deque<Node> stack = new LinkedList<>();
        stack.push(root);
        if(root == null) return list;
        while(! stack.isEmpty()){// The top node of the current stack exits the stack
            Node node = stack.pop();
            // Add values to the list
            list.add(node.val);
            int size = node.children.size();
            // Push the children of the current node from right to left
            for(int i = size - 1; i >= 0; i--){ stack.push(node.children.get(i)); }}returnlist; }}/ / recursion
class Solution {
    public List<Integer> preorder(Node root){
        List<Integer> list = new ArrayList<>();
        helper(root, list);
        return list;
    }
    public void helper(Node root, List<Integer> list){
        if(root == null) return;
        list.add(root.val);
        for(Node child: root.children){ helper(child, list); }}}Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️