java - 从递归方法返回时需要帮助

Question

我正在尝试跟踪二叉树(不是二叉搜索树)中节点的路径。给定一个节点，我尝试打印从根开始的路径值。

我写了下面的程序。

package dsa.tree;

import java.util.Stack;

public class TracePath {
    private Node n1;

    public static void main(String args[]){
        TracePath nodeFinder = new TracePath();
        nodeFinder.find();
    }

    public void find(){
        Tree t = getSampleTree();
        tracePath(t,n1);
    }

    private Tree getSampleTree() {
        Tree bsTree = new BinarySearchTree();
        int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45};
        for(int i=0;i<randomData.length;i++){
            bsTree.add(randomData[i]);
        }
        n1 = bsTree.search(76);
        return bsTree;
    }

    public void tracePath(Tree t, Node node){
        trace(t,node);
    }

    Stack<Node> mainStack = new Stack<Node>();

    public void trace(Tree t, Node node){
        trace(t.getRoot(),node);
    }

    private void trace(Node parent, Node node){
        mainStack.push(parent);
        if(node.data == parent.data){
            for(Node iNode:mainStack){
                System.out.println(iNode.data);
            }
            return;
        }
        if(parent.left != null){
            trace(parent.left, node);
        }
        if(parent.right!=null){
            trace(parent.right, node);
        }
        mainStack.pop();
    }
}

我正在正确获取输出。但有点乱。如果您看到方法 trace(Node, Node)，我正在打印我不应该做的值。我希望跟踪方法正确完成。至少，我应该在遇到 if 条件的阶段终止递归结构。

请指教。

Answer 1

好的，一旦找到节点，就需要终止递归。很简单。更改您的跟踪方法以返回一个 boolean 值，告诉我们是否找到了节点。这样，我们在找到节点后立即返回树。

private boolean trace(Node parent, Node node){
    mainStack.push(parent);
    if(node.data == parent.data){
        for(Node iNode:mainStack){
            System.out.println(iNode.data);
        }
        return true;
    }
    if(parent.left != null){
        if (trace(parent.left, node)) return true;
    }
    if(parent.right!=null){
        if (trace(parent.right, node)) return true;
    }
    mainStack.pop();
    return false;
}