二叉树-后序遍历

• 按照 左、右、中 的顺序进行遍历

  • 位于中间的父节点最后，因此叫后序

• 递归方法【常用】

  function postOrderTraversal(root) {
      const res = [];
      let postOrderTraverseNode = (node) => {
          if (!node) return;
          postOrderTraverseNode(node.left);
          postOrderTraverseNode(node.right);
          res.push(node.key);
      }
      postOrderTraverseNode(root);
      return res;
  }
  

• 迭代方法，也叫栈方法

  • 和前序遍历差不多，不过利用了倒序插入res的方式，然后让left先入这样就会后出，这样就能在res中占据先头地位，实现左右中的后序遍历

  function postOrderTraversalByStack(root) {
      if (!root) return [];
      const res = [];
      const stack = [root];
      while(stack.length > 0) {
          let topNode = stack.pop();
          res.unshift(topNode.key);
          if (topNode.left) {
              stack.push(topNode.left);
          }
          if (topNode.right) {
              stack.push(topNode.right);
          }
      }
      return res;
  }