Leetcode Answers 236

接上一道题,如果只是一个二叉树,没balance,可能存在重复val,怎么找LCA?

题目:
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 v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

1
2
3
4
5
6
7
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

思路:
这里的BT就很明显并不是个BST,也不是个balanced,而且还有一点其实这里没有体现,就是node里的val可能存在重复。所以这边尽管可以借鉴一下前一题的方法,但是要记得比较的是node而不是node.val。另外一点要注意的就是,这里的traversal的想法是,先找到p / q,然后找它的parent,最后一路找上去,应该算是post order?

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = LowestCommonAncestor(root.left, p, q);
TreeNode right = LowestCommonAncestor(root.right, p, q);
if(left != null && right != null) return root;
return left == null ? right : left;
}
}

考察:这道题的变体包括之前IBM面试遇到的,如果不允许node是它自己的descendent的话怎么办?如果不是二叉树而是三叉树呢?如果common ancestor还要看其他的属性呢?我慢慢想想。。。

以上。

17-04-25
@Sturbridge