145.二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

Solution

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }

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

tips：逆后序遍历 根—->右—->左

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public void reversePreorder(TreeNode root) {
        if (root == null) {
            return;
        }
        
        System.out.print(root.val + " ");
        // 递归遍历右子树
        reversePreorder(root.right);
        // 递归遍历左子树
        reversePreorder(root.left);
      
        
    }
}

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    List <Integer> list =new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
    Stack <TreeNode> stack=new Stack<>();
    Map <TreeNode,Integer> flag =new HashMap<>();
    while(root!=null||stack.isEmpty()==false){
           if(root!=null){
               stack.push(root);
               flag.put(root,1);
               root=root.left;
           }else {
             root=stack.peek();
               if(flag.get(root)==1){
                   flag.put(root,2);
                   root=root.right;
                   
               }else{
                   root=stack.pop();
                   list.add(root.val);
                   root=null;
               }
           }


    }
    return list;
    }
}