236. Lowest Common Ancestor of a Binary Tree

原题链接：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

代码实现如下：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;/*** Created by clearbug on 2018/2/26.*/
public class Solution {public static void main(String[] args) {Solution s = new 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);return left == null ? right : right == null ? left : root;}/*** 方法一：这是我自己想的方法，何其复杂啊！！！提交之后运行结果：StackOverFlowException** @param root* @param p* @param q* @return*/public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {if (root == null || p == null || q == null) {return null;}Stack pStack = new Stack<>();Stack qStack = new Stack<>();if (!getNodePath(root, p, pStack)) {return null;}if (!getNodePath(root, q, qStack)) {return null;}Queue pQueue = new LinkedList<>(pStack);Queue qQueue = new LinkedList<>(qStack);TreeNode lca = null;while (!pQueue.isEmpty() && !qQueue.isEmpty()) {if (pQueue.peek() != qQueue.peek()) {break;}lca = pQueue.peek();pQueue.poll();qQueue.poll();}return lca;}private boolean getNodePath(TreeNode root, TreeNode target, Stack stack) {if (root == target) {return true;}stack.push(root);if (root.left != null) {if (getNodePath(root.left, target, stack)) {return true;} else {stack.pop();}}if (root.right != null) {if (getNodePath(root.right, target, stack)) {return true;} else {stack.pop();}}return false;}
}