Lowest Common Ancestor of a Binary Tree II
找LCA.
这个题看了半天和I的区别, 发现只是没有要求p和q一定在树里. check一下就可以了.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
/** * 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) { boolean l = check(root, p); boolean k = check(root, q); if(!l || !k) return null; return find(root, p, q); } private boolean check(TreeNode root, TreeNode p) { if(root == null) return false; if(root == p) return true; return check(root.left, p) || check(root.right, p); } private TreeNode find(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) // found p or q or touch the ground return root; // search p and q from left and right TreeNode left = find(root.left, p, q); TreeNode right = find(root.right, p, q); if (left != null && right != null) // from root's left & right we found both p and q, so root is the LCA return root; else // left is not null means from left's left & right we found both q and q // so left is the LCA, otherwise, right is the answer return left != null ? left : right; } } |