乐趣区

关于java:二叉树查找父节点和全部祖先节点

FYI

树形构造

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {val = x;}
}

遍历的办法

@Test
public void test() {
    TreeNode root, TreeNode p;
    // TODO 初始化 root, p;
    Stack<TreeNode> pParents = new Stack<>();
    getParents(root, p, pParents);
    // p 的父节点以及全副先人节点都寄存在 pParents 中了。}

public boolean getParents(TreeNode root, TreeNode p, Stack<TreeNode> stack) {if (root == null) {return false;}

    // System.out.println("root:" + root.val);
    if (root == p) {stack.push(root);
        // 找到了
        return true;
    }

    stack.push(root);
    if(getParents(root.left, p, stack)){return true;}
    if(getParents(root.right, p, stack)){return true;}
    // 没找到节点,还原现场
    stack.pop();

    return false;
}
退出移动版