题目描述

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).”

Note:

All of the nodes’ values will be unique.
p and q are different and both values will exist in the binary tree.

样例

Example 1:

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:

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.

递归标记法

(DFS) $O(n)$

使用dfs寻找最近祖先比较方便，原因是使用递归式的dfs时，当发现p和q分别在两个子树中时，当前访问的节点就是最近公共祖先

然后我设计了state作为标记，当下面两颗子树遍历分别返回1时，则更新结果，若单个返回2，则结果已经存在变量中，直接返回即可，当访问的节点为p或q时，state加1，由于可能出现p在q的子树中或q在p的子树中，所以对自身的判断放在递归之后，并且要再检查state是否为2

时间复杂度分析：dfs $O(n)$

Your runtime beats 99.4 % of cpp submissions
Your memory usage beats 94.55 % of cpp submissions (16.5 MB)

C++ 代码

/*
* @lc app=leetcode id=236 lang=cpp
*
* [236] 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 *result;

    int lowest(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        int state = 0;
        if (root == nullptr)
        {
            return state;
        }
        state += lowest(root->left, p, q);
        if (state == 2)
        {
            return 2;
        }

        state += lowest(root->right, p, q);
        if (state == 2)
        {
            result = result ? result : root;
            return 2;
        }

        if (root == p || root == q)
        {
            state++;
            if (state == 2)
            {
                result = result ? result : root;
                return 2;
            }
        }

        return state;
    }

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        lowest(root, p, q);
        return result;
    }
};