- 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 | tmp |

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 | /** |

1 | class Solution { |

我的代码实现：

1 | /** |

方法二:

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 | TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { |

Python

1 | def lowestCommonAncestor(self, root, p, q): |

Or using that None is considered smaller than any node:

1 | def lowestCommonAncestor(self, root, p, q): |

Ruby

1 | def lowest_common_ancestor(root, p, q) |

Java

1 | public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { |

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

Java/Python iterative solution

Python

1 | def lowestCommonAncestor(self, root, p, q): |

Java

1 | public class Solution { |

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 | def lowestCommonAncestor(self, root, p, q): |

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 | def lowestCommonAncestor(self, root, p, q): |

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 | class Solution { |

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

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

1 | class Solution { |

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

Very simple dfs c++ solution , only 10 lines

1 | TreeNode * dfsTraverse(TreeNode * root, TreeNode * p , TreeNode * q) |

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

Short and clean C++ solution

Want to share my solution.

1 | TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { |