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).”
_______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.
Python Solution:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
def recu(root, p, q):
if not root: return 0, None
l, left = recu(root.left, p, q)
if l == 3: return 3, left
r, right = recu(root.right, p, q)
if r == 3: return 3, right
if root == p: cur = 1
elif root == q: cur = 2
else: cur = 0
return cur + l + r, root
val, node = recu(root, p, q)
if val == 3: return node
C Solution 1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode *postorder(struct TreeNode *root, struct TreeNode *p, struct TreeNode *q, int *val) {
if (!root) {
*val = 0;
return 0;
}
int left;
struct TreeNode *l = postorder(root->left, p, q, &left);
if (left == 3) {
*val = 3;
return l;
}
int right;
struct TreeNode *r = postorder(root->right, p, q, &right);
if (right == 3) {
*val = 3;
return r;
}
int cur = 0;
if (root == p) cur = 1;
else if (root == q) cur = 2;
*val = cur + left + right;
return *val == 3 ? root : 0;
}
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
int val;
return postorder(root, p, q, &val);
}
C Solution 2:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
if (!root || root == p || root == q) return root;
struct TreeNode *left = lowestCommonAncestor(root->left, p, q);
struct TreeNode *right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root;
return left ? left : right;
}
Summary:
- pre, in, post can almost always solve problem.
- but C Solution 2 is so beautiful, and it's not pre or in or post.
近期评论