【算法题解】43. 二叉树的后序遍历

爱被打了一巴掌 2024-03-16 23:50 9阅读 0赞

> 这是一道 **简单** 题  
>   
> https://leetcode.cn/problems/binary-tree-postorder-traversal/

### 题目 ###

给你一棵二叉树的根节点 `root` ，返回其节点值的 **后序遍历** 。

**示例 1：**

![e53b5a68459c70921345bce2ea0a848a.png][]

输入：root = [1,null,2,3]
    输出：[1,3,2]

**示例 2：**

输入：root = []
    输出：[]

**示例 3：**

输入：root = [1]
    输出：[1]

**提示：**

*  树中节点数目在范围  \[ 0 , 100 \] \[0, 100\] \[0,100\] 内
 *   − 100 < = N o d e . v a l < = 100 -100 <= Node.val <= 100 −100<=Node.val<=100

**进阶：**递归算法很简单，你可以通过迭代算法完成吗？

--------------------

### 递归解法 ###

不管是 [二叉树的前序遍历  
][Link 1]、 [二叉树的中序遍历  
][Link 2]还是本题要求的后序，递归是最简单也是最基本的实现。

##### Java 代码实现 #####

##### Go 代码实现 #####

/**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func postorderTraversal(root *TreeNode) (ans []int) {
        
        var dfs func(node *TreeNode)
    
        dfs = func(node *TreeNode){
        
            if node == nil {
        
                return
            }
            dfs(node.Left)
            dfs(node.Right)
            ans = append(ans, node.Val)
        }
    
        dfs(root)
    
        return ans
    }

##### 复杂度分析 #####

**时间复杂度：** O ( N ) O(N) O(N)，`N` 为二叉树中的节点个数，每个节点都需要访问一次，总计 `N` 次。  
  
**空间复杂度：** O ( N ) O(N) O(N)，`N` 为二叉树中的节点个数，空间复杂度取决于递归调用栈的深度，最大为 `N`。

--------------------

### 迭代解法 ###

后序遍历的顺序为 **左 -> 右 -> 根**，只要还有左节点，就一直往左边找下去。  
![image.png][]

翻译成代码实现，以 **Java** 为例，`stack` 代表栈，用于记录走过的路径。

while(root != null){
        
        stack.push(root);
        root = root.left;
    }

当走到最左边的节点（如`节点4`）入栈后，因为其已经没有左节点了，所以可以出栈并记录答案。  
![image.png][image.png 1]

根据入栈顺序，下一个出栈的应该是 `节点2` , 但是此时我们并不能记录 `节点2` 的值，因为他还有右节点，根据后序遍历的顺序（**左 -> 右 -> 根**），此时我们应该先遍历其右子树。那么此时 `节点2` 就不应该出栈，但是刚才 `节点4` 是直接出栈的，处理方式有冲突，怎么办呢？

我们可以注意到，`节点4` 没有右节点，而 `节点2` 有右节点，所以我们根据他的右节点是否为空来判断一下，为空就弹出栈并记录答案。不为空就不弹出，而是继续把他的右子树根据规则入栈。  
![image.png][image.png 2]

还是以 **Java** 代码为例，其中 `ans` 是用于记录答案的列表。

TreeNode top = stack.peek();
    TreeNode root = top.right;
    // 当右节点为空，记录答案，并出栈。
    if(root == null){
        
        ans.add(top.val);
        stack.pop();
    }else{
        
        // 当右节点不空，根据规则，继续入栈。
        while(root != null){
        
        	stack.push(root);
            root = root.left;
        }
    }

`节点5` 出栈规则和左边节点是一样的，只要其没有右节点，就可以直接出栈并记录答案。  
![image.png][image.png 3]

**接下来是比较关键的一点**，当 `节点2` 出栈的时候，根据上面的规则会发现其包含右节点（`节点5`）, 需要将 `节点5` 重新入栈，但是 `节点5` 刚才已经计算过了，怎么办？

最最简单的办法就是把所有记录过的节点都存起来，遇到记录过的就不管了。如计算 `节点2` 的时候，发现其 `右节点5` 已经计算过了，那么 `节点2` 就可以出栈并计入答案了。

其实**还有一个更简单的办法**，我们不需要把所有记录过的节点都存起来。

我们只需要知道上一个出栈的节点就可以了，因为根据规则（**左 -> 右 -> 根**），**如果某个节点包含右节点，那么上一个出栈的肯定是他的右节点**。

那么出栈规则就演化为：**只要其右节点为空或者上一个出栈的就是其右节点**，那么这个根节点就也可以出栈并计入答案了。

TreeNode top = stack.peek();
    TreeNode root = top.right;
    if(root == null || root == pre){
        
        ans.add(top.val);
        stack.pop();
        pre = top;
    }

![d9a8c75387a59c5a013fcc7a2972d19c.png][]

##### Java 代码实现 #####

/**
     * 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> ans = new ArrayList<>();
            Deque<TreeNode> stack = new LinkedList<>();
    
            while(root != null){
        
                stack.push(root);
                root = root.left;
            }
    
            TreeNode pre = null;
            while(!stack.isEmpty()){
        
                TreeNode top = stack.peek();
                root = top.right;
                if(root == null || root == pre){
        
                    ans.add(top.val);
                    stack.pop();
                    pre = top;
                }else{
        
                    while(root != null){
        
                        stack.push(root);
                        root = root.left;
                    }
                }
            }
            return ans;
        }
    
    }

##### Go 代码实现 #####

/**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func postorderTraversal(root *TreeNode) (ans []int) {
        
    
        stack := []*TreeNode{
        }
    
        for root != nil {
        
            stack = append(stack, root)
            root = root.Left
        }
    
        var pre *TreeNode
    
        for len(stack) > 0 {
        
            top := stack[len(stack) - 1]
            root = top.Right
            if root == nil || root == pre {
        
                ans = append(ans, top.Val)
                stack = stack[:len(stack) - 1]
                pre = top
            }else {
        
                for root != nil {
        
                    stack = append(stack, root)
                    root = root.Left
                }
            }
        }
    
        return ans
    }

### 复杂度分析 ###

**时间复杂度：** O ( N ) O(N) O(N)，`N` 为二叉树中的节点个数，每个节点都需要访问一次，总计 `N` 次。  
  
**空间复杂度：** O ( N ) O(N) O(N)，`N` 为二叉树中的节点个数，空间复杂度取决于调用栈的深度，最大为 `N`。

[e53b5a68459c70921345bce2ea0a848a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7e7643d2719b446bafcb0c113087e199.png
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzU1OTYwMjk1OQ==&mid=2247488080&idx=1&sn=81a89a88ecb4df72bf9d9fb771bbb620&chksm=fc159e30cb6217268453e77492260462325361f11a56fd71f0d419eb10ef137356efe38a11d7&token=832630894&lang=zh_CN#rd
[Link 2]: https://mp.weixin.qq.com/s?__biz=MzU1OTYwMjk1OQ==&mid=2247488050&idx=1&sn=c312da05cbad4037c496fe1a56071612&chksm=fc159e52cb62174434f48bf78a18a7b395674bcf231710b0071b8a73daf84a2eab2923f86189&token=832630894&lang=zh_CN#rd
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f59470c6d65a491cad4b2cab9ce74cab.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5a45ce8754574e5587245f63343a20fe.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0ae2ef96e4c041dab89fd52b3b2c61e8.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/9b9f6258034f4c82aedc0038512c75db.png
[d9a8c75387a59c5a013fcc7a2972d19c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d135d97a5e4846ada6e305742d299d46.png