I. Title Description:

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.

Quote: leetcode-cn.com/problems/lo…

236. The most recent common ancestor of binary trees

Ii. Analysis of Ideas:

  1. First, if the root node is empty or the root node and P or the root node and q are the same node, return the root node directly.

  2. Consider recursively checking whether P and Q are in the left or right subtree of the root;

  3. There are three main scenarios to consider

Let’s say I use this binary tree down here;

1 / \ 2 3 / \ 4 5 6Copy the code
  • Case 1:

If root, P, and Q are 1, 2, and 3 respectively.

If root is the same node as p or q, return root.

  • Situation 2:

If root, P, and Q are 1, 5, and 6 respectively

The first call to lowestCommonAncestor leftNode is: 2

So the first call to lowestCommonAncestor rightNode is: 3

And then it becomes case 1 and it eventually returns to root

  • Case 3:

If root, P, and Q are 1, 3, and 6 respectively. (p, q are both in the left and right subtrees of root is the same logic)

So the left subtree of root called lowestCommonAncestor will get leftNode nil after all;

Then the left subtree of root will call lowestCommonAncestor and get rightNode 3 after all;

We return to rightNode 3.

Iii. AC Code:



class Solution {
    func lowestCommonAncestor(_ root: TreeNode? ._ p: TreeNode? ._ q: TreeNode?). -> TreeNode? {
        // If the root node is empty or the root node is the same as p or q, return the root node directly
        if (root = = nil || root = = = p || root = = = q) {
            return root;
        }
        let leftNode : TreeNode? = lowestCommonAncestor(root?.left, p, q);
        let rightNode : TreeNode? = lowestCommonAncestor(root?.right, p, q);
        if (leftNode = = nil) {
            return rightNode;
        }
        if (rightNode = = nil) {
            return leftNode;
        }
        returnroot; }}Copy the code

4. Refer to the learning website

Binary tree

This article is participating in the “Gold Digging march Campaign”, click to see the details of the campaign