LeetCode 145. 二叉树的后序遍历【c++/java详细题解】

iamyoung001 发布于2021-09-09 09:33 / 2331人阅读

摘要：样例如样例所示，该二叉树的后序遍历为，下面来讲解递归的做法。二叉树的后序遍历顺序为左右根，因此我们直接按照左子树右子树根节点的方式遍历这颗二叉树。具体过程如下对于二叉树中的当前节点将当前节点压入栈中，并记录到数组中。

1、题目

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

示例:

输入: [1,null,2,3]     1    /     2    /   3 输出: [3,2,1]

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

2、思路1

(递归） $O (n)$

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

样例：

如样例所示，该二叉树的后序遍历为res = [9,5,7,4,3]，下面来讲解递归的做法。

二叉树的后序遍历顺序为：左->右->根，因此我们直接按照 左子树—>右子树—>根节点的方式遍历这颗二叉树。

递归函数设计：

void dfs(TreeNode* root)

root是当前访问的节点。

递归边界：

当访问到空节点时，结束本次递归调用。

具体过程如下：

1、定义res数组用来存贮访问后的节点。
2、从根节点root开始递归。
3、递归调用dfs(root->left)和dfs(root->right)来遍历当前root节点的左右子树。
4、将当前root节点的val值加入res数组中。

时间复杂度分析： $O (n)$ ，其中 $n$ 是二叉树的节点数。每一个节点恰好被遍历一次。

3、c++代码

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    vector<int>res;    vector<int> postorderTraversal(TreeNode* root) {        dfs(root);        return res;    }    void dfs(TreeNode* root)    {        if(root == NULL) return;        dfs(root->left);        dfs(root->right);        res.push_back(root->val);    }};

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

5、思路2

(迭代) $O (n)$

迭代算法的本质是模拟递归，只不过递归使用了系统栈，而在迭代算法中我们使用stack模拟系统栈。在 144. 二叉树的前序遍历题中，我们已经知道了前序遍历二叉树的迭代写法，因此如何更改少量的代码实现二叉树的后序遍历？

二叉树的前序遍历顺序为：根->左->右，后序遍历的顺序为：左->右->根，我们将后序遍历的顺序颠倒过来为：根->右->左。因此我们只需要模拟前序遍历的过程，并将前序遍历中的左右子树遍历过程对换，最后将遍历得到的res数组翻转即可得到后序遍历的结果。

具体过程如下：

对于二叉树中的当前节点root：

1、将当前节点压入栈中，并记录到res数组中。
2、如果当前节点还有右儿子的话，继续将其右儿子压入栈中。
3、重复上述过程，直到最后一个节点没有右儿子为止。

这样，我们就将当前节点root和它的右侧子节点全部访问完毕了（相当于我们已经访问了根节点和右子树节点），栈中存放着当前节点和它的全部右侧子节点。接下来我们该要去访问当前节点的左子树了，由于栈是先进后出的，此时栈顶元素的左子节点就是下一个要遍历的节点，因此

1、取出栈顶元素的左子节点，并将其弹出栈。
2、如果当前栈顶元素的左子节点不为空，我们继续将其当成当前节点root，重复对当前节点root的处理过程。
3、最后将得到的res数组翻转。

时间复杂度分析： $O (n)$ ，其中 $n$ 是二叉树的节点数。每一个节点恰好被遍历一次。

6、c++代码

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector<int> postorderTraversal(TreeNode* root) {        vector<int> res;        stack<TreeNode*> stk;        while (root || stk.size()) {            while (root) {                res.push_back(root->val);                stk.push(root);                root = root->right;            }            root = stk.top()->left;            stk.pop();        }        reverse(res.begin(), res.end());        return res;    }};

7、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> res = new ArrayList<Integer>();       Stack<TreeNode> stk = new Stack<TreeNode>();       while(root != null || !stk.isEmpty())       {           while(root != null)           {               res.add(root.val);               stk.add(root);               root = root.right;           }           root = stk.pop();           root = root.left;       }       Collections.reverse(res);       return res;   }}

原题链接： 145. 二叉树的后序遍历

云服务器混合云二叉树的遍历 java二叉树的构建二叉树的存储二叉树的存储结构

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/119633.html

LeetCode通关：连刷三十九道二叉树，刷疯了！⭐四万字长文搞定二叉树，建议收藏！⭐

分门别类刷算法，坚持，进步！刷题路线参考：https://github.com/youngyangyang04/leetcode-master 大家好，我是拿输出博客来督促自己刷题的老三，这一节我们来刷二叉树，二叉树相关题目在面试里非常高频，而且在力扣里数量很多，足足有几百道，不要慌，我们一步步来。我的文章很长，你们收藏一下。二叉树基础二叉树是一种比较常见的数据结构，在开始刷二叉树...

honhon 2021-09-04 16:45 评论0 收藏0
leetcode-145-Binary Tree Postorder Traversal

摘要：栈的意义价值具有时间性，先进后出。比如递归的后序遍历，先序遍历，二叉树的按层次打印。根据需求不同，在中暂时储存的元素单元也不同，元素的先后顺序也不同。应用对顺序有要求的数据。 stack 栈的意义价值：具有时间性，先进后出。所以具有时间关联顺序的元素可以通过这个时间。比如递归的后序遍历，先序遍历，二叉树的按层次打印。根据需求不同，在stack中暂时储存的元素...

Pandaaa 2019-07-30 17:30 评论0 收藏0
【数据结构初阶之二叉树】：二叉树相关的性质和经典的习题（用C语言实现，附图详解）

摘要：当集合为空时，称该二叉树为空二叉树。也就是说，如果一个二叉树的层数为，且结点总数是，则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。 ...

Martin91 2021-11-24 09:39 评论0 收藏0
【递归+迭代详解】二叉树的morris遍历、层序遍历、前序遍历、中序遍历、后序遍历

摘要：递归解法由于层次遍历的递归解法不是主流，因此只介绍前三种的递归解法前序遍历递归递归中序遍历递归递归后序遍历递归递归三种递归遍历的总结递归终止的条件为碰到空节点。目录分析二叉树的前序，中序，后序的遍历步骤 1.层序遍历方法一：广度优先搜索 (以下解释来自leetcode官方题解) 方法...

niceforbear 2021-11-16 11:45 评论0 收藏0
推导二叉树的遍历结果

摘要：推导前序序列已知二叉树的中序序列是，后序序列是，求前序序列。二叉树的中序序列是按照左子树，根，右子树的顺序排列的，根将左子树的序列和右子树的序列分割在左右两边。推导前序序列已知二叉树的中序序列是ABCDEFG，后序序列是BDCAFGE，求前序序列。思路 showImg(https://segmentfault.com/img/bVW1es?w=723&h=431); 二叉树的后序...

joy968 2019-08-21 17:10 评论0 收藏0