使用javascript编写预订单遍历代码
使用javascript编写预订单遍历代码
提问于 2016-08-10 01:15:13
var preorderTraversal = function(root) {
var array = [];
if(!(root == null)){
array.push(root.val) ;
preorderTraversal(root.left);
preorderTraversal(root.right);
}
return array;
};测试用例为% 1，%2时代码测试失败，我只输出%1，该如何修复？
回答 2
Stack Overflow用户
发布于 2018-06-01 05:12:36
问题是，您在每个递归调用中创建了一个新的、独立的数组(然后丢弃它，因为您不会对递归调用返回的内容做任何操作)。
另一种方法是传入一个“累加器”数组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;
};Stack Overflow用户
发布于 2018-02-23 09:40:59
您需要一个助手函数来实现js的内联打印；这个助手函数应该调用您实际的preorder函数。
在您的preorder函数内部，您需要始终更新字符串"passed“(稍后我将解释"”)。如果当前节点为空，则应返回当前拥有的字符串，否则会将其擦除。
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。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/38856834
复制相关文章
相似问题
腾讯云开发者
