右子树递归

Question

为了更灵活地编写代码，我每天都在尝试做不同的问题，但这一次却让我停滞不前。

下面的代码应该是在预序遍历中从给定的字符串建立一个二叉树。即“5 3 1 N N N 7 N N”表示下面的二叉树。元素之间用空格分隔，N标记空节点，空节点正好为NULL。

             5
            / \
          3     7
         /
        1

它应该像遍历拆分的字符串一样简单，当找到“n”以外的东西时，就用该值构造一个节点，并增加索引。

增加index之后，我再次将下一个数组元素放入左侧子树中。如果遇到“n”，则不需要执行任何操作，因为节点的构造函数已经将左子级设置为null，因此我只增加索引。理论上，正确的节点应该在前面的递归步骤中分配...但不知怎的，这就失败了？

是因为JavaScript的异步行为吗？我错过了什么？

提前感谢您的帮助！

class Node {
    constructor(val) {
        this.val = val;
        this.left = this.right = null;
    }
}

class Index {
    constructor() {
        this.index = 0;
    }
    incr() {
        this.index++;
    }
}

function deserialize(treeString) {
    let treeArray = treeString.split(" ");
    let index = new Index();
    let length = treeArray.length;
    function helper(index) {
        if (index.index < length) {
            let node = null;
            if (treeArray[index.index] !== "N") {
                node = new Node(parseInt(treeArray[index.index], 10));
                index.incr();
                node.left = helper(index);
                node.right = helper(index);
            } else {
                index.incr();
            } 
            return node;
        };
    }
    return helper(index);
}

Answer 1

我不明白您的错误，因为console.log(json.stringify(deserialize('5 3 1 N N N 7 N N'),null,1))给了我

{
    "val": 5,
    "right": {
        "val": 7,
        "right": null,
        "left": null
    },
    "left": {
        "val": 3,
        "right": null,
        "left": {
            "val": 1,
            "right": null,
            "left": null
        }
    }
}

这似乎是你想要的结果

我们可以做一些“更简单”的事情

1. 防止自己进行无用的缩进

特别是对于递归条件下的停止，最好先写它们

function recurse(){
    if (index.index == length) {
        //stop code
        return 
    }
    //your other conditions...
    //your code which will call recurse
}

2.1这里的“迭代器”没用

由于您仍然依赖于了解您的结构（treeArray必须“实现”运算符[])，因此使用哑变量至少会减少代码

2.2如果您真想使用迭代器

您可以看到，无论在if或else路径中，您都包含（这相当于“在treearray中前进”）。所以只需在TreeArray上迭代即可。下面我们“pop”元素（向前）

function helper(arr){
    if end
        return
    let currentNodeVal = arr.shift() //advance in treeArray
    if (currentNodeVal !== "N") {
        node = new Node(parseInt(currentNodeVal, 10));
        node.left = helper(arr);
        node.right = helper(arr);
    } else {
        //nothing to do
    } 
}

这里实际上没有任何异步代码在运行。如果您命名为

helperinfty = function(){
    while(true){}
}
node.left = helperinfty(arr)
node.right = helper(arr);

您可以观察到node.right=helper(arr)从未执行过。当您使用settimeout等时（简单地说，当函数需要回调来同步流时），您就会得到“时髦”的东西（答案是否定的）

打印与开头相同的树

class Node {
    constructor(val) {
        this.val = val;
        this.left = this.right = null;
    }
}

function deserialize(treeString) {
    let arr = treeString.split(" ");
    function helper(arr) {
        if(arr.length == 0)return null;//note that in previous implem helper "could" return undefined...which is not something desired
        let current = arr.shift();
        if (current == "N"){
            //this is a matter of preference. Arguably one can prefer your style.
            //I prefer to emphase that when N is found it is meant to be a null node, and "abort" any recursion
            return null
        }
        let node = new Node(parseInt(current, 10));
        node.left = helper(arr);
        node.right = helper(arr);
        return node;
    }
    return helper(arr);
}
x = deserialize('5 3 1 N N N 7 N N');
console.log(JSON.stringify(x, null, 4))