# 236. (LCA) Lowest Common Ancestor of a Binary Tree

![](/files/-MlL32yojfTlxzdow-r7)

![](/files/-MlL35xf_B5mTrfWkhSo)

time: O(n)

space:O(n)

```java
/*
    236. Lowest Common Ancestor of a Binary Tree

    1. 終止條件
    2. 找左子樹
    3. 找右子樹
    4. 如果在左右子樹找到pq, 代表pq一個在左一個在右, root就會是LCS
    5. 如果只有在某一邊找到, 代表pq在同一側, 所以LCS就是某一邊找到的本身結果（題目中有提到LCS可以是p或q本身）

    time complexity: O(n), space complexity: O(n)

 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p.equals(root) || q.equals(root) {
            return root; // 1.terminal condition, find p,q or not find pq => null
        }
        
        TreeNode left = lowestCommonAncestor(root.left, p, q); //2.find left side for p, q
        TreeNode right = lowestCommonAncestor(root.right, p, q); //3.find right side for p, q

        if (left != null && right != null) {
            return root; // 4.if find p,q in left and right side, root is LCS !
        }
        return left != null ? left : right; // 5.if only one side find p or q (it means p,q are all in one side), it's the answer because in question we allow a node to be a descendant of itself
    }
}
```

另一個思路, 用 count, 其實一樣啦...

```java
class Solution {
    TreeNode res = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p, q);
        return res;
    }
    private int dfs(TreeNode node, TreeNode p, TreeNode q) {
        if (node == null) {
            return 0;
        }
        int left = dfs(node.left, p, q);
        int right = dfs(node.right, p, q);
        int self = (node.val == p.val || node.val == q.val) ? 1 : 0;
        int count = left + right + self;
        if (count == 2 && res == null) {
            res = node;
        }
        return count;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/tree/lca/236.-lowest-common-ancestor-of-a-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.