How to find the nearest common ancestor of a binary tree in Java

Idea 1: First assume that this tree is a binary search tree

First of all, let’s add a supplementary explanation of what a binary search tree is:

In a binary search tree, for each For a node, the values ​​in its left subtree are smaller than it, and the values ​​in its right subtree are larger than it. So the in-order traversal of a binary search tree is an ordered set of data.

#For the above tree, assume that the nearest common ancestor of p q is required.

Then it has the following situations:

For ordinary binary trees, there are nothing more than these situations. : pq are all on the left, pq are all on the right, pq is one on the left and one on the right, and one of pq is the root node.

So recursively go to the left subtree and right subtree to find the common ancestor of the p q node. If it is found, the node will be returned. If it is not found, it will return empty.

##Based on the above ideas, we can easily write the code

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null) return null;

    // p 为当前树的根节点
    if(p == root) return p;
    // q 为当前树的根节点
    if(q == root) return q;
    
    // 去左子树中找
    TreeNode left = lowestCommonAncestor(root.left,p,q);
    // 去右子树中找
    TreeNode right = lowestCommonAncestor(root.right,p,q);

    // 左边右边都找到了
    if(left != null && right != null) {
        return root;
    }
    // 左边找到了，右边没找到
    if(left != null) {
        return left;
    }
    if(right != null) {
        return right;
    }
    return null;
}

Idea 2: Assume that the tree uses the child parent representation

Each node will save the address of its father node, which can be searched online layer by layer until the first intersection point of the two linked lists is found, and the intersection point is theirs common ancestor.

For an ordinary binary tree, you can only search down layer by layer, not upward, so you need to keep the paths of the two nodes until the last one of the two paths is the same. node. Here we use a stack to retain the paths of two nodes.

First pop the elements in the stack with more elements, and then pop the two stacks together until the nodes to be popped are equal, which is their nearest common ancestor.

The biggest difficulty here is the storage path.

Here a stack is used to store the path. When a node is traversed, the node is put into the stack, and then the left tree and right tree of the node are recursively searched. If the path is found, the path is retained. If not found, the path is retained. pop up.

Suppose you are looking for p in the figure below:

#First put the root node into the stack, recursively search for the left subtree of the root node, and pop it up if it is not found. , find in the right subtree.

When root reaches 6, it is found that the left and right sides of the node are empty, indicating that the target node is not found in the subtree, and 6 pops up, on the right of 5 Continue searching in the subtree.

Similarly, it cannot be found in the right subtree of 5. It will pop up until it goes to the right subtree of 3 and finds 1.

// 用于找节点的路径
public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
    if(root == null || node == null) {
        return false;
    }
    // 将当前节点放入栈中
    stack.push(root);
    
    if(root.val == node.val) {
        return true;// 找到了
    }
    // 当前节点没找到，去左子树找
    boolean flag = getPath(root.left,node,stack);
    // 左子树中找到了，直接返回
    if(flag) {
        return true;
    }
    // 左子树没找到，去右子树找
    flag = getPath(root.right,node,stack);
    // 右子树中找到了，直接返回
    if(flag) {
        return true;
    }
    
    // 左右子树都没找到，弹出节点
    stack.pop();
    return false;

}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null) {
        return null;
    }
    Stack<TreeNode> stackp = new Stack<>();
    Stack<TreeNode> stackq = new Stack<>();

    // 分别得到  p q 的路径
    getPath(root,p,stackp);
    getPath(root,q,stackq);

    int sizep = stackp.size();
    int sizeq = stackq.size();

    if(sizep > sizeq) {
        int size = sizep - sizeq;
        // 弹出元素直至两栈中元素个数相等
        while(size > 0) {
            stackp.pop();
            size--;
        }
    }else {
        int size = sizeq - sizep;
        // 弹出元素直至两栈中元素个数相等
        while(size > 0) {
            stackq.pop();
            size--;
        }
    }

    // 一起弹出，直到找到第一个相同的元素
    while(!stackp.isEmpty() && !stackq.isEmpty()) {
        if(stackp.peek() == stackq.peek()) {
        	// 找到了，就返回该节点
            return stackq.pop();
        }else {
            stackp.pop();
            stackq.pop();
        }
    }
    // 没找到，返回 null
    return null;
}

The above is the detailed content of How to find the nearest common ancestor of a binary tree in Java. For more information, please follow other related articles on the PHP Chinese website!