236. Lowest Common Ancestor of a Binary Tree

发表于 | 更新于: | 分类于 | 本文总阅读量 次
| 字数统计: 1,741 | 阅读时长 ≈ 11
  • 29.6%

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/#/description

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
8
tmp
        _______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.

这道题，还有其他解法，可以思考方法二中的代码

重点题目

解法一：

我的代码实现：

Dec 10th, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr || root==p || root==q)
            return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left && right)
            return root;
        return left!=nullptr?left:right;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
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 && right)
            return root;
        return left? left:right;
    }
};

我的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 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* 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 && right)
            return root;
        return left?left:right;
    }
};

方法二:

http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

https://discuss.leetcode.com/topic/18561/4-lines-c-java-python-ruby

4 lines C++/Java/Python/Ruby

Same solution in several languages. It’s recursive and expands the meaning of the function. If the current (sub)tree contains both p and q, then the function result is their LCA. If only one of them is in that subtree, then the result is that one of them. If neither are in that subtree, the result is null/None/nil.

Update: I also wrote two iterative solutions now, one of them being a version of the solution here. They’re more complicated than this simple recursive solution, but I do find them interesting.

C++

1
2
3
4
5
6
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    return !left ? right : !right ? left : root;
}

Python

1
2
3
4
5
def lowestCommonAncestor(self, root, p, q):
    if root in (None, p, q): return root
    left, right = (self.lowestCommonAncestor(kid, p, q)
                   for kid in (root.left, root.right))
    return root if left and right else left or right

Or using that None is considered smaller than any node:

1
2
3
4
5
def lowestCommonAncestor(self, root, p, q):
    if root in (None, p, q): return root
    subs = [self.lowestCommonAncestor(kid, p, q)
            for kid in (root.left, root.right)]
    return root if all(subs) else max(subs)

Ruby

1
2
3
4
5
6
def lowest_common_ancestor(root, p, q)
    return root if [nil, p, q].index root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    left && right ? root : left || right
end

Java

1
2
3
4
5
6
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);
    return left == null ? right : right == null ? left : root;
}

https://discuss.leetcode.com/topic/27479/java-python-iterative-solution

Java/Python iterative solution

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def lowestCommonAncestor(self, root, p, q):
    stack = [root]
    parent = {root: None}
    while p not in parent or q not in parent:
        node = stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)
    ancestors = set()
    while p:
        ancestors.add(p)
        p = parent[p]
    while q not in ancestors:
        q = parent[q]
    return q

# 31 / 31 test cases passed.
# Status: Accepted
# Runtime: 108 ms
# 99.14%

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        parent.put(root, null);
        stack.push(root);

        while (!parent.containsKey(p) || !parent.containsKey(q)) {
            TreeNode node = stack.pop();
            if (node.left != null) {
                parent.put(node.left, node);
                stack.push(node.left);
            }
            if (node.right != null) {
                parent.put(node.right, node);
                stack.push(node.right);
            }
        }
        Set<TreeNode> ancestors = new HashSet<>();
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }
        while (!ancestors.contains(q))
            q = parent.get(q);
        return q;
    }
}

To find the lowest common ancestor, we need to find where is p and q and a way to track their ancestors. A parent pointer for each node found is good for the job. After we found both p and q, we create a set of p’s ancestors. Then we travel through q’s ancestors, the first one appears in p’s is our answer.

https://discuss.leetcode.com/topic/18652/iterative-solutions-in-python-c

Iterative Solutions in Python/C++

Solution 1

Same algorithm as my recursive solution (look there if you want some explanation), but iterative. I do a post-order traversal with a stack. Each stack element at first is a [node, parent] pair, where parent is the stack element of the node’s parent node. When the children of a parent get finished, their results are appended to their parent’s stack element. So when a parent gets finished, we have the results of its children/subtrees available (its stack element at that point is [node, parent, resultForLeftSubtree, resultForRightSubtree]).

1
2
3
4
5
6
7
8
9
10
11
12
13
def lowestCommonAncestor(self, root, p, q):
    answer = []
    stack = [[root, answer]]
    while stack:
        top = stack.pop()
        (node, parent), subs = top[:2], top[2:]
        if node in (None, p, q):
            parent += node,
        elif not subs:
            stack += top, [node.right, top], [node.left, top]
        else:
            parent += node if all(subs) else max(subs),
    return answer[0]

Solution 2

Here I find the paths to p and q and then find the last node where the paths match. I just came up with the path-building technique for this, and I find it quite neat and maybe it could be useful elsewhere.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def lowestCommonAncestor(self, root, p, q):
    def path(root, goal):
        path, stack = [], [root]
        while True:
            node = stack.pop()
            if node:
                if node not in path[-1:]:
                    path += node,
                    if node == goal:
                        return path
                    stack += node, node.right, node.left
                else:
                    path.pop()
    return next(a for a, b in zip(path(root, p), path(root, q))[::-1] if a == b)

C++ version of Solution 1

I don’t use C++ much, so maybe there’s room for improvement with stuff that I don’t know.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    struct Frame {
        TreeNode* node;
        Frame* parent;
        vector<TreeNode*> subs;
    };
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        Frame answer;
        stack<Frame> stack;
        stack.push({root, &answer});
        while (stack.size()) {
            Frame *top = &stack.top(), *parent = top->parent;
            TreeNode *node = top->node;
            if (!node || node == p || node == q) {
                parent->subs.push_back(node);
                stack.pop();
            } else if (top->subs.empty()) {
                stack.push({node->right, top});
                stack.push({node->left, top});
            } else {
                TreeNode *left = top->subs[0], *right = top->subs[1];
                parent->subs.push_back(!left ? right : !right ? left : node);
                stack.pop();
            }
        }
        return answer.subs[0];
    }
};

https://discuss.leetcode.com/topic/20063/accepted-24ms-dfs-c-solution-only-3-lines

Accepted 24ms DFS c++ solution, only 3 lines.

1
2
3
4
5
6
7
8
class Solution {
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
	    if (root == p || root == q || root == NULL) return root;
	    TreeNode *left = lowestCommonAncestor(root->left, p, q), *right = lowestCommonAncestor(root->right, p, q);
	    return left && right ? root : left ? left : right;
    }
};

https://discuss.leetcode.com/topic/18786/very-simple-dfs-c-solution-only-10-lines

Very simple dfs c++ solution , only 10 lines

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TreeNode * dfsTraverse(TreeNode * root, TreeNode * p , TreeNode * q)
{
    if( root == p || root == q || root == NULL)
        return root;
    TreeNode * parent1 = dfsTraverse(root->left, p, q);
    TreeNode * parent2 = dfsTraverse(root->right, p, q);
    if( parent1 && parent2)
        return root;
    else
        return parent1 ? parent1:parent2;
}
TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * p, TreeNode * q)
{
    return dfsTraverse(root, p, q);
}

https://discuss.leetcode.com/topic/26396/short-and-clean-c-solution

Short and clean C++ solution

Want to share my solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
    if (!root || !p || !q) {
        return NULL;
    }
    
    if (root == p || root == q) {
        return root;
    }
    
    TreeNode* l = lowestCommonAncestor(root->left, p, q);
    TreeNode* r = lowestCommonAncestor(root->right, p, q);
    
    if (l && r) {
        return root;
    }
    
    return l? l : r;
}
谢谢你，可爱的朋友。