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

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();
    }
}

我正确地得到了输出.但它有点凌乱.如果你看到方法跟踪(节点,节点),我打印的是我不应该做的值.我希望跟踪方法正确完成.至少,我应该在遇到if条件的阶段杀死递归结构.

请指教.

Answer 1

好的,你需要在找到节点后终止递归.很简单.更改trace方法以返回一个布尔值,告诉我们是否找到了节点.这样,我们在找到节点后立即回到树上.

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;
}