[binary tree] - middle order traversal of binary tree

Binary tree

Order traversal in binary tree

Middle order traversal idea

Official understanding ：

First of all, we need to know what is the middle order traversal of binary tree ： Follow to visit the left subtree —— The root node —— The right subtree traverses the tree , When we visit the left subtree or the right subtree, we traverse in the same way , Until you walk through the whole tree

author ：LeetCode-Solution
link ：https://leetcode.cn/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

Personal understanding ：

• First, judge whether the binary tree is empty , If it is empty , Then return the empty string

• If the binary tree is not empty （ loop / recursive ）

  1. First access the root node , Then access the left child node of the root node , Access the left child node of the left child node , Until a node has no left child node , This node is output

  2. Determine whether the node has a right child node , If there is , Is to 1 operation , without , Go back to the root node of this node

  3. Then access the root node , Output the root node

  4. Then access the right child node of the root node , If the right child node exists , Then repeat 1, without , Then return to the root node of the root node , Conduct 1 operation

The illustration

1. Judge that the binary tree is not empty
2. visit A, visit A The left child of B, visit B The left child of D, visit D The left child of G, visit G The left child of , here G The left child node of does not exist , So the output G
3. look for G Right child of ,G The right child of does not exist
4. look for G The root node D, Output D
5. Revisit D Right child of H,H The left child node of does not exist , So the output H
6. look for H Right child of ,H The right child of does not exist , So back to D node
7. look for D The root node of the node B, Output B
8. B The right child node of the node does not exist , So back to B
9. look for B The root node A, Output A, look for A Right child of C
10. look for C The left child of E, look for E The left child of , There is no such thing as E The left child of , So the output E
11. look for E Right child of I, look for I The left child of , non-existent , So the output I
12. look for I Right child of , non-existent , So back to E node
13. look for E The root node of the node C, Output C
14. look for C Right child of node F, look for F The left child of , The left child node does not exist , So the output F
15. look for F Right child of node , non-existent , So back to C, At this point, the tree traversal is completed

Finally, the middle order traversal of the graph is output as

G	D	H	B	A	E	I	C	F

Code implementation

• Ideas 1： Use recursion to implement

/** *  The time and space utilization of this method are O(n) * * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    public List<Integer> inorderTraversal(TreeNode root) {
    
        //  establish list Save results 
        List<Integer> result = new ArrayList<Integer>();
        //  Connect the root node to result Pass in , Do middle order traversal 
        access(root, result);
        return result;
    }

    public void access(TreeNode root, List result){
    
        //  Determine if the two tree is empty 
        if(root == null){
    
            return ;
        }
        //  Find the left child node 
        access(root.left, result);
        //  Output root node （ Here, the node without left and right child nodes can be regarded as the root node output ）
        result.add(root.val);
        //  Find the right child node 
        access(root.right,result);
    }
}

• Train of thought two ： Cyclic iteration method

public List<Integer> inorderTraversal(TreeNode root){
    
        //  establish list Save results 
        List<Integer> result = new ArrayList<Integer>();

        //  establish stack Stack to save the pressing order 
        Stack<TreeNode> stack = new Stack();

        //  If root Not empty , Will continue to be pushed into the stack , If root It's empty , The node will pop up from the stack 
        //  there root It is changing. , Don't interpret it as the root node of the entire tree , It is the root node of each subtree 
        while(root != null || !stack.isEmpty()){
    
            //  When the current node is not empty , Push in the left child node of this node , Until the left child node does not exist 
            while(root != null){
    
                stack.push(root);
                root = root.left;
            }
            //  Pop up the left child node just pressed 
            root = stack.pop();
            //  Output the result 
            result.add(root.val);
            //  Consider whether the right child node of this node is empty , If it is empty , Continue to pop up , If it's not empty , The right child node is regarded as a right subtree , Repeat the above operation 
            root = root.right;
        }

        return result;
    }