LeetCode236（二叉树的最近公共祖先）

发表于 | 分类于 ，

题目：

　　给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

思路：

　　此题最开始无法想出思路。结合官方解答后做出。同时递归法难想到，比较巧妙，难理解。

代码：

递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode236 {
	private TreeNode LCA;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        recurseTree(root, p, q);
        return LCA;
    }
    public boolean recurseTree(TreeNode root, TreeNode p, TreeNode q) {
    	if (root == null) {
			return false;
		}
    	int left = recurseTree(root.left, p, q)?1:0;
    	int right = recurseTree(root.right, p, q)?1:0;
    	int mid = (root == p || root == q)?1:0;
    	if (left + right + mid >= 2) {
			this.LCA = root;
		}
    	return (left + right + mid) > 0;
    }
}

复杂度分析及总结：

递归：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。