This is the 13th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Hello, everybody, today is the 13th day of my August more article, in the previous article, we have done the most recent public ancestor of binary search tree, today we will do the title of the most recent public ancestor of binary tree, see how the two methods of solving, the text is as follows:

The title

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

The definition of recent common ancestor is as follows: “For the two nodes P and Q of the root tree T, the recent common ancestor is expressed as a node X, where 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).

For example, a given binary tree as follows: root = [3,5,1,6,2,0,8, null, null, 7, 4]

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 most recent common ancestor node can be the node itself.Copy the code

Their thinking

Assuming root is the closest common ancestor of P, q, then there are three possible situations:

  1. P and Q are in the subtree of root, and respectively in the left and right subtree of root.
  2. P = root, and q is in the left or right subtree of root;
  3. Q = root, and p is in the left or right subtree of root;

Here, we use the binary tree preorder traversal method to search the binary tree; Returns when a node p or q is encountered. Backtracking from bottom to top, when nodes P and q are on different sides of node root, node root is the most recent public ancestor, and then return to root upward.

Recursive function analysis:

  1. Termination condition: when the root node is encountered, null is returned. Return root if root is equal to p or q.
  2. Single-layer recursive logic: turn on the left child node of recursion, return value as left; Turns on the recursive right child and returns the value right.
  3. Return value: if both left and right are null, p and q are not found, null is returned; If both left and right are not null, then p and q are located on both sides of root, so root is the nearest ancestor node, and root is returned. If left is null and right is not null, then p and q are not in the left subtree of root, then right is returned directly. Otherwise, left is returned.

Code implementation

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(root == null || root == p || root == q){
            return root;
        }

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

        if (right == null) {
            return left;
        }

        returnroot; }}Copy the code

The last

Complexity analysis

  • Time complexity: O(N), where NN is the number of nodes in the binary tree. All nodes of a binary tree are accessed only once, so the time complexity is O(N).

  • Space complexity: O(N), where N is the number of nodes in the binary tree. The stack depth of a recursive call depends on the height of the binary tree, which in the worst case is a chain with height N, so the space complexity is O(N).