二叉树-中序遍历

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

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

• 递归方法【常用】

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

• 迭代方法，也叫栈方法

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