二叉树的后序遍历
- https://leetcode.cn/problems/binary-tree-postorder-traversal/
描述
- 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2
输入：root = []
输出：[]
示例 3
输入：root = [1]
输出：[1]
提示
- 树中节点的数目在范围 [0, 100] 内
- -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
算法实现
1 ）方案 1
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function postorderTraversal(root: TreeNode | null): number[] {
const result: number[] = []
const isValid = (val: any) => val !== null;
const postorderHandler = (root: TreeNode | null) => {
if(!root) return result;
isValid(root.left) && postorderHandler(root.left);
isValid(root.right) && postorderHandler(root.right);
isValid(root.val) && result.push(root.val);
return result;
}
return postorderHandler(root)
};
- 同前序和中序，这是递归版，递归版真香, 代码及其简洁, 缺点也很明显
- 后续遍历特点
- 对根节点的左子树进行后续遍历
- 对根节点的右子树进行后续遍历
- 访问根节点
- 记忆：左右根
2 ）方案 2
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function postorderTraversal(root: TreeNode | null): number[] {
if(!root) return [];
const res: number[] =[];
const stack: TreeNode[] = [];
let cur = root;
stack.push(root);
while(stack?.length) {
cur = stack.pop()!;
res.push(cur.val);
if(cur.left) stack.push(cur.left);
if(cur.right) stack.push(cur.right);
}
return res.reverse();
};
- 这是官方提供的示例，迭代版本，使用栈的特性：后进先出
- 这里用到一个逆向思维，从顶点开始，而非从叶子节点开始
- 根节点值先进栈，之后左节点入栈，之后右节点入栈
- 当while继续时，右节点先出栈(后进先出) 并压进结果栈
- 之后继续找右节点的左右节点，循环处理，直到没有孩子节点
- 在一个最小规模的场景下，比如一棵树只有左右根，那么这个顺序就是
-
根右左，这是最小规模的场景，也是我们的切入点
- 这样reverse之后就是 左右根 这样的顺序了
- 之前是从根节点开始的，这样就把顺序捋正了，从叶子节点开始
- 这个是一种新的思路
3 ）方案
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function postorderTraversal(root: TreeNode | null): number[] {
const ans = <number[]>[]; // 存放最终集合
const stack = <TreeNode[]>[]; // 存放树节点集合的栈
let cur = root; // 当前节点
while(cur || stack.length) {
while(cur) {
ans.push(cur.val); // 根的值
stack.push(cur);
cur = cur.right; // 右节点
}
if(stack.length){
cur = stack.pop();
cur = cur.left; // 左节点
}
}
return ans.reverse();
}
- 这是前序遍历方案2和本方案2结合的思路
- 先访问最深层根叶子节点，用一个栈进行来回捯饬
- 最后在用一个reverse进行反转，这也提供一种新的思路
