145. 二叉树的后序遍历 🟩

题目

LeetCode 简单

题目

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

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

题解

方法：递归

递归 O(n) O(n)

function postorderTraversal(root: TreeNode | null): number[] {
  let res = []
  if (root) {
    const postorder = (node: TreeNode) => {
      if (node.left) postorder(node.left)
      if (node.right) postorder(node.right)
      res.push(node.val)
    }
    postorder(root)
  }
  return res
}

const tree = new Tree([3, 9, 20, null, null, 15, 7, 14, 13])
console.log('🌰', tree)
console.log('🌰', postorderTraversal(tree.root))

方法：迭代

栈 O(n) O(n)

function postorderTraversal(root) {
  let res = []

  if (root) {
    const stack = [root]
    const outputStack = []

    while (stack.length) {
      console.log('stack', JSON.stringify(stack.map(i => i.val)))
      console.log('outputStack', JSON.stringify(outputStack.map(i => i.val)))

      const n = stack.pop()
      outputStack.push(n)
      if (n.left) stack.push(n.left)
      if (n.right) stack.push(n.right)

      console.log('---')
    }

    console.log('最后 outputStack', JSON.stringify(outputStack.map(i => i.val)))

    while (outputStack.length) {
      const n = outputStack.pop()
      res.push(n.val)
    }
  }
  return res
}

// function postorderTraversal(root) {
//     if (!root) return [];
//     const result = [];
//     const stack =[root];

//     while (stack.length > 0) {
//         const node = stack.pop();
//         result.push(node.val);

//         // 与前序相反，这里先压左，再压右，出栈顺序就是先右再左
//         if (node.left) stack.push(node.left);
//         if (node.right) stack.push(node.right);
//     }

//     // 最后把结果翻转
//     return result.reverse();
// }

// 定义二叉树节点
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

// 构建一棵测试用的二叉树
//        1
//      /   \
//     2     3
//    / \   / \
//   4   5 6   7
const root = new TreeNode(1)
root.left = new TreeNode(2, new TreeNode(4), new TreeNode(5))
root.right = new TreeNode(3, new TreeNode(6), new TreeNode(7))

console.log('🌰', postorderTraversal(root))

执行结果

stack [1]
outputStack []
---
stack [2,3]
outputStack [1]
---
stack [2,6,7]
outputStack [1,3]
---
stack [2,6]
outputStack [1,3,7]
---
stack [2]
outputStack [1,3,7,6]
---
stack [4,5]
outputStack [1,3,7,6,2]
---
stack [4]
outputStack [1,3,7,6,2,5]
---
最后 outputStack [1,3,7,6,2,5,4]
🌰 [4,5,2,6,7,3,1]

本页目录