二叉树-先序遍历

• 按照 中、左、右 的顺序进行遍历，本质是DFS

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

• 递归方法【常用】

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

• 迭代方法，也叫栈方法

  • 优先取得中间的node，然后让right先入这样就会后出，使实现中左右的后序遍历

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