使用javascript编写预序遍历

Question

var preorderTraversal = function(root) {
    var array = [];
    if(!(root == null)){
       array.push(root.val) ;
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }
    return array;
};

当测试用例为[1,2]时，代码测试失败，我只输出[1]，如何解决？

Answer 1

问题是您在每个递归调用中创建了一个新的、单独的数组（然后丢弃它，因为您不对递归调用返回的内容做任何事情）。

另一种方法是传入一个“累加器”数组 acc，并将其传递给每个递归调用，以便将所有元素添加到单个数组中：

var preorderTraversal = function(root, acc = []) {
   if(!!root){
      acc.push(root.val);
      if (root.left) preorderTraversal(root.left, acc);
      if (root.right) preorderTraversal(root.right, acc);
   }
   return acc;
};

您可能还对pre-ordered BST迭代遍历而不是递归遍历感兴趣：

var preorderTraversal = function(root) {
   /**
    * Algorithm:
    * 1. Create an empty stack [];
    * 2. Do while stack is not empty:
    * 2.1. Pop an item from stack and add it to the 'result' array.
    * 2.2. Push 'right child' of popped item to stack.
    * 2.3. Push 'left child' of popped item to stack.
   */
   if (root == null) {
     return [];
   }

   const stack = [];
   const result = [];

   stack.push(root);

   while(stack.length > 0) {
     let current = stack.pop();
     result.push(current.val);

     if (current.right) stack.push(current.right);
     if (current.left) stack.push(current.left);
   }

   return result;
};

Answer 2

array 是一个局部变量，那么：

1. 你用push把1放到数组上
2. 再次创建时递归到其他边 array = []
3. 推2
4. 当你返回到递归堆栈顶部时，数组仍然只有 1

如果您可以发送数组作为参数，并使用返回的数组来修改本地数组，也许会更好