LeetCode 236 Lowest Common Ancestor of a Binary Tree (LCA)

本文主要是介绍LeetCode 236 Lowest Common Ancestor of a Binary Tree (LCA)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1/  \2    3/ \    \4   5    7

After calling your function, the tree should look like:

         1 -> NULL/  \2 -> 3 -> NULL/ \    \4-> 5 -> 7 -> NULL

 

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

题目分析：巨暴力的方法就是看两个点是不是在同一个子树中，一旦不在则表示当前的子树根就是LCA，900ms+

 

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Solution {public boolean hasTreeNode(TreeNode root, TreeNode tar) {if (root == null) {return false;}if (root == tar) {return true;}return hasTreeNode(root.left, tar) || hasTreeNode(root.right, tar);}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || (root.left == null && root.right == null)) {return root;}if (p == root || q == root) {return root;}boolean pInLeft = hasTreeNode(root.left, p);boolean qInLeft = hasTreeNode(root.left, q);if (pInLeft && qInLeft) {return lowestCommonAncestor(root.left, p, q);}else if (!pInLeft && !qInLeft) {return lowestCommonAncestor(root.right, p, q);}else {return root;}}
}

其实仔细一想，上面两个递归的过程可以合成一个，分别在左右子树中找p和q，若一边全没找到则答案肯定在另一边，由于LCA是最近的公共祖先所以要自底向上以后序遍历的方式来查找

5ms，时间击败100%

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public 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);TreeNode right = lowestCommonAncestor(root.right,  p,  q);if (left == null) {return right;} else if (right == null) {return left;}return root;}
}

 

 

这篇关于LeetCode 236 Lowest Common Ancestor of a Binary Tree (LCA)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---