145. 二叉树的后序遍历
145. 二叉树的后序遍历
🟢 🔖 栈
树
深度优先搜索
二叉树
🔗 力扣
LeetCode
题目
Given the root
of a binary tree, return the postorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Constraints:
- The number of the nodes in the tree is in the range
[0, 100]
. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
题目大意
给你二叉树的根节点 root
,返回它节点值的 后序 遍历。
进阶:递归算法很简单,你可以通过迭代算法完成吗?
解题思路
思路一:递归
后序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后再打印它的右子树,最后打印这个节点本身。而在访问左子树或者右子树的时候,按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,可以直接用递归函数来模拟这一过程。
- 先递归调用
preorderTraversal(root.left)
来遍历root
节点的左子树 - 再递归调用
preorderTraversal(root.right)
来遍历root
节点的右子树 - 最后将
root
节点的值加入答案即可 - 递归终止的条件为碰到空节点
复杂度分析
时间复杂度:
O(n)
,其中n
是二叉树的节点数。每一个节点恰好被遍历一次。空间复杂度:
O(n)
,为递归过程中栈的开销,平均情况下为O(logn)
,最坏情况下树呈现链状,为O(n)
。
思路二:迭代
也可以用迭代的方式实现思路一的递归函数,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而迭代的时候需要显式地将这个栈模拟出来,其余的实现与细节都相同,具体可以参考下面的代码。
先序遍历是中左右,后续遍历是左右中,那么我们只需要调整一下先序遍历的代码顺序,就变成中右左的遍历顺序,然后再反转 res 数组,输出的结果顺序就是左右中了。
复杂度分析
时间复杂度:
O(n)
,其中n
是二叉树的节点数。每一个节点恰好被遍历一次。空间复杂度:
O(n)
,为迭代过程中显式栈的开销,平均情况下为O(logn)
,最坏情况下树呈现链状,为O(n)
。
代码
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function (root) {
let res = [];
if (root == null) return res;
res.push(...postorderTraversal(root.left));
res.push(...postorderTraversal(root.right));
res.push(root.val);
return res;
};
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function (root) {
let res = [];
if (root == null) return res;
let stack = [root];
while (stack.length) {
let node = stack.pop();
res.unshift(node.val);
if (node.left) stack.push(node.left);
if (node.right) stack.push(node.right);
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
94 | 二叉树的中序遍历 | [✓] | 栈 树 深度优先搜索 1+ | 🟢 | 🀄️ 🔗 |
590 | N 叉树的后序遍历 | [✓] | 栈 树 深度优先搜索 | 🟢 | 🀄️ 🔗 |
2477 | 到达首都的最少油耗 | 树 深度优先搜索 广度优先搜索 1+ | 🟠 | 🀄️ 🔗 |