/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return null;
boolean leftHasP = hasDescendant(root.left, p.val);
boolean leftHasQ = hasDescendant(root.left, q.val);
boolean rightHasP = hasDescendant(root.right, p.val);
boolean rightHasQ = hasDescendant(root.right, q.val);
if (root.val == p.val || root.val == q.val)
return root;
if ((leftHasP && rightHasQ) || (leftHasQ && rightHasP))
return root;
if (!leftHasP && !leftHasQ)
return lowestCommonAncestor(root.right, p, q);
else
return lowestCommonAncestor(root.left, p, q);
}
private boolean hasDescendant(TreeNode root, int val) {
if (root == null)
return false;
if (root.val == val) {
return true;
}
if (hasDescendant(root.left, val) || hasDescendant(root.right, val)) {
return true;
}
return false;
}
}Feel free to share your thoughts in comments, below!
No comments:
Post a Comment