var preorderTraversal = function(root) {
var array = [];
if(!(root == null)){
array.push(root.val) ;
preorderTraversal(root.left);
preorderTraversal(root.right);
}
return array;
};
测试用例为% 1,%2时代码测试失败,我只输出%1,该如何修复?
发布于 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;
};
发布于 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。
https://stackoverflow.com/questions/38856834
复制相似问题