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