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

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; } }; ``````