二叉树的后序遍历

发表于
本文字数： 2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，145. Binary Tree Postorder Traversal

先看题目描述

大意就是给定二叉树，让我们返回其后根遍历序列

算法和思路

就按照左子树-右子树-根节点的顺序遍历二叉树就行，用递归或栈都能实现，不过用栈实现时实际上是逆序的后根遍历

算法源码

递归

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
29
30
31
32
33
import java.util.ArrayList;
import java.util.List;

/**
 * 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 {
    List<Integer> res = new ArrayList<>();
    
    public List<Integer> postorderTraversal(TreeNode root) {
        dfs(root);
        return res;
    }
    
    private void dfs(TreeNode root) {
        if (root == null) return;;
        dfs(root.left);
        dfs(root.right);
        res.add(root.val);
    }
}

栈

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
29
30
31
32
33
34
35
import java.util.ArrayList;
import java.util.List;

/**
 * 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 {
    List<Integer> res = new ArrayList<>();
    
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        stack.add(root);
        while (!stack.isEmpty()) {
            root = stack.removeLast();
            res.add(0, root.val);
            if (root.left != null) stack.add(root.left);
            if (root.right != null)  stack.add(root.right);
        }
        return res;
    }
}