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