二叉树的后序遍历

[louzhedong]

习题

出处 LeetCode 算法第145题

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

示例:

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

输出: [3,2,1]

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

思路

解法一：递归遍历，比较简单

解法二：非递归方式，使用一个栈按照p, p.right, p.left来保存需要遍历的节点，再一个个出栈

解答

//方法一：递归
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
function helper(root, res) {
  if (root.left) {
    helper(root.left, res);
  }
  if (root.right) {
    helper(root.right, res);
  }
  res.push(root.val);
}
var postorderTraversal = function (root) {
  var res = [];
  if (!root) return res;
  helper(root, res);
  return res;
};

// 方法二：非递归
var postorderTraversal = function (root) {
  var res = [];
  if (!root) return res;
  var stack = [];
  var pointer = root;
  var last = root;
  stack.push(pointer);
  while (stack.length > 0) {
    pointer = stack[stack.length - 1];
    if ((pointer.left == null && pointer.right == null) || (pointer.right == null && last == pointer.left) || (last == pointer.right)) {
      res.push(pointer.val);
      last = pointer;
      stack.pop();
    } else {
      if (pointer.right) {
        stack.push(pointer.right);
      }
      if (pointer.left) {
        stack.push(pointer.left);
      }
    }
  }
  return res;
};