25. Middle order traversal of binary tree

94. Middle order traversal of binary trees

The difficulty is simple 1030

Given the root node of a binary tree root , Back to its Middle preface Traverse .

Example 1：

 Input ：root = [1,null,2,3]
 Output ：[1,3,2]

Example 2：

 Input ：root = []
 Output ：[]

Example 3：

 Input ：root = [1]
 Output ：[1]

Example 4：

 Input ：root = [1,2]
 Output ：[2,1]

Example 5：

 Input ：root = [1,null,2]
 Output ：[1,2]

recursive

If the current node is not empty , Then recursively put the values of all nodes of the left subtree into ans in , Then put the value of the current node into ans in , Then recursively put the values of all nodes of the right subtree into ans in

Definition inorder(root) Indicates that the current traversal to \textit{root}root The answer to the node , So by definition , We just call recursively inorder(root.left) To traverse \textit{root}root The left subtree of the node , And then \textit{root}root The value of the node is added to the answer , And recursively call inorder(root.right) To traverse \textit{root}root The right subtree of the node can be , The condition for the termination of recursion is to hit an empty node .

Code

class Solution {
    
    public List<Integer> inorderTraversal(TreeNode root) {
    
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> res) {
    
        if (root == null) {
    
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

iteration ( Advanced ) Left root right ·

Press the leftmost chain of the whole lesson tree into the stack , Every time you take out the top element of the stack , And record the top element of the stack , If it has a right subtree , Then press the right subtree into the stack .

/** * 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) {
    
        List<Integer> ans = new ArrayList<Integer>();
        Stack<TreeNode> stk = new Stack<TreeNode>();
        TreeNode p = root;
        while(p!=null||!stk.isEmpty()){
    
            while(p!=null){
    
                stk.add(p);
                p = p.left;
            }
            p = stk.pop();
            ans.add(p.val);
            p = p.right;
        }
        return ans;



    }
}