Task

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]

leetcode236

Example

Example 1:

1
2
3

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

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，说明该节点即为所求
    • 若只有左子树或右子树中能找到p或q，就返回能找到p或q的那个子节点
    • 若左子树和右子树中都不能找到p或q，则返回空
  • 时间复杂度：每个节点看一次，O(n)
  • 空间复杂度：取决于树的高度，O(h)
 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

// Runtime: 20 ms, faster than 89.51% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.
// Memory Usage: 14.5 MB, less than 37.39% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.
/**
 * 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/空节点
        if(!root || root==p || root==q) return root;
        //遍历左右子树，找左右子树中的LCA
        //实际返回时，若一棵子树中含有p或q，就返回该子树的根节点（根据递归终止条件）
        TreeNode *l=lowestCommonAncestor(root->left,p,q);
        TreeNode *r=lowestCommonAncestor(root->right,p,q);
        //若左右子树都返回了有效节点，说明左右子树中都找到了p或q，该节点为所求
        if(l && r)
            return root;
        //若左右子树中只有一个能找到p或q，就返回那棵子树
        //若左右子树都找不到p或q，就返回空节点
        else
            return l?l:r;
        
    }
};