preface

Here is the previous swipe card records, you can have a look, if you have any different views and views or feel what is wrong, welcome to leave a message in the comment area! 🙏 🙏 🙏

[LeetCode0303 topic area and retrieval – array immutable] | punch brush

[LeetCode1200. Minimum absolute difference] | punch brush

[LeetCode0304 topic 2 d area and retrieval – matrix immutable] | punch brush

[LeetCode11 topic containers of most water] | punch brush

[LeetCode0338 topic bit count] | punch brush

[LeetCode209 topic length minimum subarray] | punch brush

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, 10^5].

  • -10^9 <= Node.val <= 10^9

  • All node.val are different.

  • p ! = q

  • Both p and q exist in a given binary tree.

Their thinking

Given a binary tree root, find the nearest common ancestor of the specified nodes P and q in root. The definition of the common ancestor is clearly explained above.

First, if root is null, or root == p or root == q, p and q are in the left and right subtrees of root, you can return root itself directly.

In the second step, p and Q are in the same subtree of root, and the left and right subtrees and p and Q nodes of root are passed to recursively search.

If the recursive result of the left subtree is null, the right subtree is returned.

If the recursive result of the right subtree is null, the left subtree is returned.

If the recursive result of both the left and right subtrees is null, p and Q are not in the left and right subtrees of root.

The problem solving code

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
   if (root === null || root === p || root === q) return root
   const left = lowestCommonAncestor(root.left, p, q)
   const right = lowestCommonAncestor(root.right, p, q)
   if (left === null) return right
   if (right === null) return left
   return root
};
Copy the code

conclusion

Do not be afraid to write bad, dare to write is already very good, the process of writing is the process of review, it is easier to deepen their understanding.

Come on! HXDM!!!!!! 💪 💪 💪

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign