This is the 27th day of my participation in Gwen Challenge

The nearest common ancestor of a binary search tree

Topic describes

Given a binary search tree, find the most recent common ancestor of two specified nodes in the tree.

The definition of the nearest common ancestor in Baidu encyclopedia is: “For the two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, satisfying that X is the ancestor of P and Q and x is as deep as possible (a node can also be its own ancestor).

For example, given the following binary search tree: root = [6,2,8,0,4,7,9, null, null, 3, 5)

Example 1:

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 8 output: 6: node 2 and 8 of recent common ancestor is 6.Copy the code

Example 2:

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 4 output: 2: recent common ancestor node 2, and 4 is 2, because recent common ancestor nodes can be according to the definition for the node itself.Copy the code

Description:

  • All nodes have unique values.
  • P and Q are different nodes and exist in the given binary search tree.

Thought analysis

Looking for the number of binary tree search a recent common ancestor of two nodes, we should make good use of the characteristics of binary search tree is on the left side of the node is less than the root node, the right of the node is greater than the root node, all at the same time as the node values are unique, p and q for different nodes and all exist in a given binary search trees. Whenever these two nodes are larger than the target node, they are to the right of the root node, and if they are both smaller than the target node, they are to the right. In addition to these two cases, we find the root node.

The code shown

Solution a:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {return null;
        }
        if(root.val > p.val && root.val > q.val){
            return lowestCommonAncestor(root.left,p,q);
        }
        if(root.val < p.val && root.val < q.val){
            return lowestCommonAncestor(root.right,p,q);
        }
        return root;

    }
Copy the code

The most recent Common Ancestor of binary trees (236)

Topic describes

Given a binary tree, find the nearest common ancestor of the two specified nodes in the tree.

The definition of the nearest common ancestor in Baidu Encyclopedia is as follows: “For two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, which satisfies that X is the ancestor of P and Q and the depth of X is as large as possible (a node can also be its own ancestor).

Example 1:

Input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, output q = 1:3: node 5 and 1 recent common ancestor node 3.Copy the code

Example 2:

Input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, q = 4 output: 5: node 5 nodes and four recent common ancestor is 5. Because by definition the nearest common ancestor node can be the node itself.Copy the code

Example 3:

Input: root = [1,2], P = 1, q = 2 Output: 1Copy the code

Tip:

  • The number of nodes in the tree is in the range [2, 105].
  • -109 <= Node.val <= 109
  • All node.val are different.
  • p ! = q
  • Both p and q exist in a given binary tree.

Thought analysis

Different from in front of the binary search tree, here is a binary tree, we can’t use the characteristics of the binary search tree, we need each node to determine, first of all, there may be a p or q is their common ancestor, and then we will have a recursive search, the nodes of the first record the left and right, nodes are found if left and right, So you’ve found the target node, if one of them doesn’t exist, then it’s not, you know all of them.

The code shown

Solution a:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(root == null) {return null;
        }
        // P or Q themselves are common ancestors
        if(root == p || root == q){
            return root;
        }
        // Recursive search, first record left and right nodes
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        // If left and right are found
        if(left ! =null&& right ! =null) {return root;
        } else if (null! = left){return left;
        } else if (null! = right){return right;
        }
        return null;
    }
Copy the code

conclusion

The most recent common ancestor of binary tree and binary search tree should be mastered and utilized.