原題鏈接：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
代碼實現(xiàn)如下：

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();}// 討論區(qū)一位高手的答案，不得不說：高手就是高手啊！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;}/*** 方法一：這是我自己想的方法，何其復(fù)雜啊！！！提交之后運行結(jié)果：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<TreeNode> pStack = new Stack<>();Stack<TreeNode> qStack = new Stack<>();if (!getNodePath(root, p, pStack)) {return null;}if (!getNodePath(root, q, qStack)) {return null;}Queue<TreeNode> pQueue = new LinkedList<>(pStack);Queue<TreeNode> 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<TreeNode> 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;}
}

轉(zhuǎn)載于:https://www.cnblogs.com/optor/p/8645576.html

總結(jié)

以上是生活随笔為你收集整理的236. Lowest Common Ancestor of a Binary Tree的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。