InterviewBit - 查找给定节点的路径

Question

我正在练习 InterviewBit 挑战 Path to Given Node，但我一直遇到问题：

首先，如果我将我的辅助函数（遍历）保留在这样的结构中，当我运行它说遍历的代码未定义时。

我尝试将函数移到 solve(A, B) 中，但它说我没有得到正确的结果。我的代码在底部。

题目很简单：找到二叉树A中节点B的路径

问题描述：

Given a Binary Tree A containing N nodes.

You need to find the path from Root to a given node B.

NOTE:

No two nodes in the tree have same data values. You can assume that B is present in the tree A and a path always exists.

Example Input

Input 1:

A =
       1
     /   \
    2     3
   / \   / \
  4   5 6   7 
B = 5

Input 2:

A =
       1
     /   \
    2     3
   / \     \
  4   5     6
B = 1

Example Output

Output 1:

[1, 2, 5]

Output 2:

[1]
// Definition for a  binary tree node
//    function TreeNode(data){
//      this.data = data
//      this.left = null
//      this.right = null
//    }

我的代码

module.exports = { 
 //param A : root node of tree
 //param B : integer
 //return a array of integers
    solve : function(A, B){
        // traverse tree
        // each traversal append a new node 
        // if the leaf is not the node, return earlier traversal
        // like if from left to right we find nothing at all, we return earlier traversal
        path = traverse(A, B, []);
        return path;
    },
    traverse: function(node, target, traversal) {
        if (node) {
            traversal.push(node.data);
            if (node.data === target) return traversal;
            traversal = traverse(node.left, target, traversal);
            traversal = traverse(node.right, target, traversal);
            traversal.pop();
        }
        return traversal;
    },
};

Answer 1

当您将traverse定义为导出对象的属性时，您需要将其调用为this.traverse()。但似乎更好的做法是将其定义为 solve.

范围内的局部函数

你随后遇到的问题是，即使你找到了一条路径，你仍然有 .pop() 个元素，所以这是行不通的。

当从找到路径的递归调用返回时，您不应该立即return进一步搜索调用者的相同路径，谁会做相同，...直到原始调用者获得该路径。

你应该避免的另一件事：不要将 path 定义为全局变量。使用 const、let 或 var.

显式声明

所以修改如下：

    solve : function(A, B){
        function traverse(node, target, traversal) {
            if (node) {
                traversal.push(node.data);
                if (node.data === target) return traversal;
                let success = traverse(node.left, target, traversal);
                if (success) return success;
                success = traverse(node.right, target, traversal);
                if (success) return success;
                traversal.pop();
            }
        }

        // Declare!
        let path = traverse(A, B, []);
        return path;

这将解决它。

现在考虑如何做得更好，避免传递第三个参数。您可以递归地使用 solve 函数并在回溯退出递归时构建正确的路径。

InterviewBit - 查找给定节点的路径

InterviewBit - Find path to given node

javascript

tree

tree-traversal

Example Input

Example Output

我的代码