首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >使用javascript编写预订单遍历代码

使用javascript编写预订单遍历代码
EN

Stack Overflow用户
提问于 2016-08-10 01:15:13
回答 2查看 2.9K关注 0票数 3
代码语言:javascript
复制
var preorderTraversal = function(root) {
    var array = [];
    if(!(root == null)){
       array.push(root.val) ;
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }
    return array;
};

测试用例为% 1,%2时代码测试失败,我只输出%1,该如何修复?

EN

回答 2

Stack Overflow用户

发布于 2018-06-01 05:12:36

问题是,您在每个递归调用中创建了一个新的、独立的数组(然后丢弃它,因为您不会对递归调用返回的内容做任何操作)。

另一种方法是传入一个“累加器”数组acc,并将其传递给每个递归调用,这样所有元素都被添加到一个数组中:

代码语言:javascript
复制
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感兴趣,而不是递归遍历:

代码语言:javascript
复制
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;
};
票数 8
EN

Stack Overflow用户

发布于 2018-02-23 09:40:59

您需要一个助手函数来实现js的内联打印;这个助手函数应该调用您实际的preorder函数。

在您的preorder函数内部,您需要始终更新字符串"passed“(稍后我将解释"”)。如果当前节点为空,则应返回当前拥有的字符串,否则会将其擦除。

代码语言:javascript
复制
function doPreOrder(root, str) {
  if(!root) {
    return str;
  }
  if(!str) {
    str = "";
  }
  if(root) {
    str += root.val + ' ';
    str = doPreOrder(root.left, str);
    str = doPreOrder(root.right, str);
  }
  return str;
}

function preOrder(root) {
  var x = doPreOrder(root);
  console.log(x);
}

如您所见,我们首先需要使用函数,并且只传递root。我们将一个未定义的变量传递给它,这将是我们唯一一次输入str = ""代码,然后从那时起,str将针对每个新数据进行更新。最后,您只需通过控制台记录该var。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/38856834

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档