题目描述

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]

 

题目大意

要求在一棵二叉树中（注意：非搜索二叉树），查找给定的两个结点的最小的父节点（所谓最小的父节点是指他们两个结点能向上找到的离他们最近的具有相同祖宗的结点）。

给的两个结点都在树结点当中，且互不相同。

 

示例

E1

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.

E2

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.

 

解题思路

基于递归思想，将当前结点分为左孩子结点和右孩子结点来分别考虑，若左孩子结点返回了空指针，则代表其右孩子结点一定包含了所有的结点，则返回右孩子结点即可。同理，若右孩子结点为空，则返回左孩子结点。若当前结点为其中一个结点，则返回当前结点即可。

 

复杂度分析

时间复杂度：O(N)

空间复杂度：O(1)

 

代码

/**
 * 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) {
        if(!root || root->val == p->val || root->val == q->val)
            return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        // 若左结点为空，则返回右结点；若右结点为空，则返回左结点，否则返回当前结点
        return !left ? right : !right ? left : root;
    }
};