145. Post order traversal of binary tree

The traversal of the tree ：

1、 breadth-first level Use the iterative method .
2、 Depth first Before the order , Middle preface , In the following order , Refers to the order of root nodes use recursive , Iterative implementation .

Three elements of recursion ：

1、 Parameters , Return value
2、 Termination conditions
3、 Every recursive logic

Recursive implementation

Before the order , Middle preface , Post sequence similar , Only the subsequent implementation is shown here .

  /**
 * 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> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList();
        digui(root,list);
        return list;
    }

    public void digui(TreeNode r ,List<Integer> list){
        if(r == null) return ;
        // Right and left 
        digui(r.left,list);
        digui(r.right,list);
        list.add(r.val);
    }
}

Iterative method

iteration , Implementation with stack .
The element to be output is out of the stack , Iterated element stack .

Iterative implementation

Preamble implementation

Press the right node first , Press the left node again , Make sure the output sequence is left first and then right .
Pay attention ： Null pointers do not need to be stacked .

/**
 * 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> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        // Iterative method 
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode t = stack.pop();
            list.add(t.val);
            if(t.right != null) stack.push(t.right);
            if(t.left != null) stack.push(t.left);
        } 
        return list;
    }
}

tip ：
Note that the boundary value is empty .

In order to achieve

First traverse the left node , Pressing stack .
There is no left node , Out of the stack , Output .
Then traverse the right node , Pressing stack .

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // In order to arrange    Left   in   Right 
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();

        if(root == null) return list;

        while(!stack.isEmpty() || cur!=null){
            if(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        
        }
        return list;
    }
}

Subsequent implementation

Before the order Around the middle In the following order Right and left
To achieve Center right left , And then reverse , Achieve left and right .

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
      // in , Right , Left 
      List<Integer> list = new ArrayList<>();
      Stack<TreeNode> stack = new Stack<>();

        if(root == null) return list;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode r = stack.pop();
            list.add(r.val);
            if(r.left != null) stack.push(r.left);
            if(r.right != null) stack.push(r.right);
        }
        Collections.reverse(list);
        return list;
    }
}

Implementation of unified iterative method

The reasons for the inconsistency in the previous text ：
Order of access , It is inconsistent with the order of traversing the returned results .
solve ： If it is an element to traverse the result , The stack is followed by a null pointer to identify .
Preorder traversal is implemented as follows , In the sequence traversal , After the sequence traversal , Just fine tune the order .
The former sequence traversal ： Around the middle . Stack order ： Right , Left , in （ Processing elements , Followed by null identification ）
In the sequence traversal ： Left middle right . Stack order ： Right , in （ Heel null identification ）, Left
After the sequence traversal ： Right and left . Deposit sequence ： in （ Heel null identification ）, Right , Left

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode t = stack.peek();
            if(t == null){
                stack.pop();
                list.add(stack.pop().val);
            }else{
                stack.pop();
                if(t.right != null) stack.push(t.right);
                if(t.left != null) stack.push(t.left);
                stack.push(t);
                stack.push(null);
            }
        }
        return list;
    }
}

Pay attention to mistakes ：
1、 The method to get the top element of the stack ：peek()
2、 Remember to traverse every node , First out of the stack , Go back to the stack . Don't just get in and out , Operation exceeded expectations .