Cousins in Binary Tree
给一个unique value的树, 找2个node是不是cousins. cousins定义是不同父但是同深度.
|
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 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isCousins(TreeNode root, int x, int y) { if(root == null) return false; int[] a = new int[2]; int[] b = new int[2]; TreeNode dummy = new TreeNode(Integer.MAX_VALUE); // dummy node for root's parent find(root, dummy, x, 0, a); // search x find(root, dummy, y, 0, b); // search y if(a[0] != b[0] && a[1] == b[1]) return true; else return false; } private void find(TreeNode root, TreeNode p, int n, int d, int[] res) { if(root == null) return; if(root.val == n) { res[0] = p.val; res[1] = d; } if(root.left != null) find(root.left, root, n, d+1, res); if(root.right != null) find(root.right, root, n, d+1, res); } } |