递归获取二叉树中节点的路径

Question

我得到的路径是错误的 - 递归不会在结束条件处停止。我有一个这样定义的树节点：

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

一棵树：

还有一个函数：

const getPath = function(root, node) {
    let path = [];

    const traverse = function(root, node) {
        if (root.left || root.right) {
            path.push(root.val);
        }
        if (root.val === node.val) {
            path.push(root.val);
            return;
        }
        if (root.left) {
            traverse(root.left, node);
        }
        if (root.right) {
            traverse(root.right, node);
        }
    };
    traverse(root, node);
    return path;
};

如果我想获取元素 7 的路径，输出将是 [3, 5, 2, 7]，因为这是从根到该节点的路径。

但是我的函数的输出是 [3, 5, 2, 7, 1] - 它似乎不会在 return 条件下停止，而是继续处理它在堆栈中的任何内容。

这段代码有什么问题？

我图片中的树示例：

const T = new TreeNode(3);
T.left = new TreeNode(5);
T.right = new TreeNode(1);
T.left.left = new TreeNode(6);
T.left.right = new TreeNode(2);
T.left.right.left = new TreeNode(7);
T.left.right.right = new TreeNode(4);
T.right.left = new TreeNode(0);
T.right.right = new TreeNode(8);


const node = T.left.right.left;
const path = getPath(T, node); // [3, 5, 2, 7, 1]

Answer 1

只有在左侧或右侧找到匹配项时才应推送。（现在，您在第一个 if 中无条件地推送。）一种可能性是仅在找到匹配项时（即，在递归找到匹配项之后，并且）将数组创建为 return你正在冒泡备份树和调用堆栈):

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}
const getPath = function(root, valToFind) {
    if (root.val === valToFind) {
        // found: create the array to return
        return [root.val];
    }
    if (root.left) {
        const result = getPath(root.left, valToFind);
        if (result) {
            // unshift: add this node's value to the beginning of the array
            result.unshift(root.val);
            return result;
        }
    }
    if (root.right) {
        const result = getPath(root.right, valToFind);
        if (result) {
            result.unshift(root.val);
            return result;
        }
    }
};

const T = new TreeNode(3);
T.left = new TreeNode(5);
T.right = new TreeNode(1);
T.left.left = new TreeNode(6);
T.left.right = new TreeNode(2);
T.left.right.left = new TreeNode(7);
T.left.right.right = new TreeNode(4);
T.right.left = new TreeNode(0);
T.right.right = new TreeNode(8);


const node = T.left.right.left;
console.log(getPath(T, node.val)); // [3, 5, 2, 7]
console.log(getPath(T, 4));
console.log(getPath(T, 8));
console.log(getPath(T, 6));

Answer 2

您可以在进行通常的预序遍历时跟踪您是否在另一个变量中找到了您的节点。根据您是否找到该节点，您可以将当前值附加到 path，或者如果在任何子树中都找不到它，则附加到 pop：

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

const getPath = function(root, node) {
  let path = [];
  let found = false;

  const traverse = function(curr) {
    if (!curr || found) return;
    if (curr.val == node.val) found = true;
    
    path.push(curr.val);
    traverse(curr.left);
    traverse(curr.right);
    if (!found) path.pop();
  };

  traverse(root, node);
  return path;
};

const T = new TreeNode(3);
T.left = new TreeNode(5);
T.right = new TreeNode(1);
T.left.left = new TreeNode(6);
T.left.right = new TreeNode(2);
T.left.right.left = new TreeNode(7);
T.left.right.right = new TreeNode(4);
T.right.left = new TreeNode(0);
T.right.right = new TreeNode(8);

console.log(getPath(T, T.left.right.left));
console.log(getPath(T, T.right.left));
console.log(getPath(T, T.left.left));

递归获取二叉树中节点的路径

Get path to a node in a binary tree recursively

javascript

binary-tree