[LeetCode]236. Lowest Common Ancestor of a Binary Tree

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1:

1
2
3
4
5
6

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Output: 3

Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

1
2
3
4
5
6

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

Output: 5

Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Note:

  • All of the nodes’ values will be unique.

  • p and q are different and both values will exist in the binary tree.

Solution

解析

二叉树的最低公共祖先,很经典的一道题。由于二叉树本身定义的递归性,所以,大部分二叉树的问题都可以使用递归来求解。因此,这里也是用递归方法来求解。

首先,分析问题。给定一颗二叉树,两个节点,找这两个节点的最低公共祖先。题目要求二叉树所有的都是不相同的,p和q两个节点不同,而且都在二叉树中。再分析,给定的两个测试用例,例子一,p和q位于root的两个不同分支上,返回root节点;例子二,q是p的子孙节点,返回p节点。

因为p和q不相同,我们在一棵二叉树中查找节点p或q,找到就返回,没找到返回null。现在根节点开始找,如果没找到,在左分支找;然后在右分支找。因为p和q唯一,p和q的查找情况有:

  • 在左分支找到p(或q),在右分支没找到q(或p)[不可能在左右分支都找到同一个点p,因为每个节点都是唯一的]———-返回p(或q),此时另一个节点是它的子孙;

  • 在左分支找到p(或q),在右分支找到q(或p)———返回根节点

  • 在左分支没找到p(或q),在右分支找到q(或p)[和情况1类似]—–返回找到的节点

  • 都没找到——-不可能[题目说明p和q是有效的,一定存在]

所以,代码如下:

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

*/

class Solution {

public:

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

// 在二叉树中找节点p和q,根据查找结果返回

// 先判断根节点是否找到,找到直接返回

// 根左分支找,找到返回这个节点node1

// 根右分支找,找到返回这个节点node2

// 因为树中不会出现两个相同的节点(值也不相同---直接比较节点地址)

// 根据返回节点判断:

// 1. 如果node1 为空,返回node2(不管空与否)

// 2. 如果node1 不为空,判断node2是否为空,空,返回node1;不为空,返回root节点



// 最低公共祖先位置一共有两种:

// 1. 两个节点之间存在祖先子孙关系,返回最高的节点(最先找到的节点)

// 2. 其他,属于不同家族,不是同一系(兄弟,or 是兄弟的子孙), 返回root

if (!root || root == p || root == q) return root;



TreeNode* node1 = lowestCommonAncestor(root->left, p, q);

TreeNode* node2 = lowestCommonAncestor(root->right, p, q);



if (!node1) return node2;

if (!node2) return node1;

return root;

}

};
您的支持就是我更新的最大动力!谢谢!