Traversal of binary tree

I haven't painted it for a long time leetcode, The anxiety of not finding a job begins again , Starting today , Pick up the topic again and live a more blog ！

Traversal of binary trees is an old saying , Interviews often occur , In terms of methods, it can be divided into recursive methods and non recursive methods , In terms of type, it can be divided into pre order, middle order and post order , And sequence, etc .

1. Preorder traversal of two tree （Leetcode 144）

a. Recursive method

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root != null){
            list.add(root.val);
            list.addAll(preorderTraversal(root.left));
            list.addAll(preorderTraversal(root.right));
        }
        return list;      
    }
}

here , I want to talk about ,List in add and addAll The difference between ：

add Is to take the passed in parameter as the current List One of them Item Storage , Even if you pass in a List It will only change the current List increase 1 Elements ;addAll It's the introduction of a List, Put this List All elements in are added to the current List in , That is, at present List The number of elements that will be added is the number of elements that are passed in List Size . namely addAll(Collection c),add(int index,Elelemt e). To put it bluntly , Namely add The following parameter is an element ,addAll The following parameter is a list.

b. Non recursive methods

Ideas ： Realize the storage node through stack , First store the nodes of the right subtree in the stack , Then store and pop up the nodes of the left subtree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root != null){
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()){
                TreeNode a = stack.pop();
                list.add(a.val);
                if(a.right != null){
                    stack.push(a.right);
                }
                if(a.left != null){
                    stack.push(a.left);
                }
            }           
        }
        return list;
    }       
}

2. Middle order traversal of binary trees （Leetcode 94）

a. Recursive method

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root != null){
            list.addAll(inorderTraversal(root.left));
            list.add(root.val);
            list.addAll(inorderTraversal(root.right));
        }       
        return list;      
    }
}

b. Non recursive methods

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            list.add(node.val);
            root = node.right;
        }
        return list;
    }
}

3. Postorder traversal of binary trees （Leetcode 145）

a. Recursive method

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root != null){
            list.addAll(postorderTraversal(root.left));
            list.addAll(postorderTraversal(root.right));
            list.add(root.val);
        }
        return list;        
    }
}

b. Non recursive methods

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
		Stack<TreeNode> nodeStack = new Stack<>();
		Stack<Integer> nodeState = new Stack<>();
        // Record whether the right node has been visited ,1 Indicates that you have visited ,0 Indicates no access to 

		 
		if(root==null)
			 return res;
		 else {
			 nodeStack.push(root);
			 nodeState.push(0);
			 root=root.left;
		}		 

		 while(!nodeStack.isEmpty()){		 
			 while(root!=null)
			 {
				 nodeStack.push(root);
				 nodeState.push(0);
				 root=root.left;
			 }// When this cycle jumps out ,  explain nodeStak The node at the top of the stack has no left node 			 

			 if(nodeState.peek()==1){
                 // If you have visited the right node at this time ,  At this time, you can access the root node 			 
				 res.add(nodeStack.pop().val);
				 nodeState.pop();// Remove the corresponding state value of the root node 				 
			 }
			 else {// Access the right node 
				root=nodeStack.peek().right;
				nodeState.pop();// Change the status value by 0 change 1  
				nodeState.push(1);
			}
		 }
		 return res;      
    }
}

4. Sequence traversal of binary tree

• Two queues , A queue holds the nodes currently to be traversed , Another queue is used to store nodes for the next traversal . Initial state the current queue has only one element root node .
• Then pop up the work queue element , If there are child nodes , Push the next traversal node . When the current queue is empty , Switch 2 The function of queues continues .
• See the picture for details 2.jpg

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        
        if(root == null)
            return ans;
        
        List<TreeNode> cur = new LinkedList<>();
        List<TreeNode> next = new LinkedList<>();
        List<TreeNode> tmp = new LinkedList<>();
        
        cur.add(root);
        while(!cur.isEmpty()){
            List<Integer> list = new LinkedList<>();
            while(!cur.isEmpty()){
                if(cur.get(0).left != null)
                    next.add(cur.get(0).left);
                if(cur.get(0).right != null)
                    next.add(cur.get(0).right);
                list.add(cur.get(0).val);
                cur.remove(0);
            }
            tmp = cur;
            cur = next;
            next = tmp;
            ans.add(list);
        }
        return ans;       
    }
}

5. Flip binary tree (Leetcode 226)

a. Recursive method

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null)
            return root;
        TreeNode node = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(node);
        return root;      
    }
}

b. Non recursive methods

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null)
            return root;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
            if(node.left != null){
                stack.push(node.left);
            }
            if(node.right != null){
                stack.push(node.right);
            }
        }
        return root;
    }
}

6. Zigzag hierarchy traverses a binary tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        
        if(root == null)
            return ans;
        
        Deque<TreeNode> cur = new LinkedList<>();
        Deque<TreeNode> next = new LinkedList<>();
        Deque<TreeNode> tmp = new LinkedList<>();
        
        cur.add(root);
        int i = 1;
        while(!cur.isEmpty()){
            List<Integer> list = new LinkedList<>();
            while(!cur.isEmpty()){
                if(i % 2 == 1){
                    if(cur.getFirst().left != null)
                        next.add(cur.getFirst().left);
                    if(cur.getFirst().right != null)
                        next.add(cur.getFirst().right);
                    list.add(cur.getFirst().val);
                    cur.removeFirst(); 

                }
                else{
                    if(cur.getLast().right != null)
                        next.addFirst(cur.getLast().right);  //addFirst Equivalent to the add The opposite position of plus 
                    if(cur.getLast().left != null)
                        next.addFirst(cur.getLast().left);
                    list.add(cur.getLast().val);
                    cur.removeLast(); 
                }                             
            }
            ++i;
            tmp = cur;
            cur = next;
            next = tmp;
            ans.add(list);
        }
        return ans;       
    }
}

7. Middle order traversal and post order traversal construct binary tree (Leetcode 106)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree1(inorder, postorder, 0, inorder.length, 0, postorder.length);
    }
    
    public TreeNode buildTree1(int[] inorder, int[] postorder, int instart, int inend, int poststart, int postend){
        if(instart >= inend)
            return null;
        int i = instart;
        while(i < inend){
            if(inorder[i] == postorder[postend - 1]){
                break;  // Find the root node 
            }
            ++i;
        }
        TreeNode root = new TreeNode(inorder[i]);
        int left_len = i - instart;  // Number of elements in the left subtree 
        root.left = buildTree1(inorder, postorder, instart, i, poststart, poststart + left_len);
        root.right = buildTree1(inorder, postorder, i + 1, inend, poststart + left_len, postend - 1);
        return root;
    }
}