Lowest Common Ancestor of a Binary Tree IV
还是找LCA, 这次是找n个node的lca
一个个找即可.
|
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 |
/** * 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[] nodes) { Set<TreeNode> set = new HashSet<>(); for(TreeNode n : nodes){ set.add(n); } return find(root, set); } private TreeNode find(TreeNode root, Set<TreeNode> set) { if(root == null) return root; if(set.contains(root)){ set.remove(root); return root; } TreeNode left = find(root.left, set); TreeNode right = find(root.right, set); if(left != null && right != null) return root; if(left == null) return right; else return left; } } |