本文主要是介绍Cousins in binary tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true
Input: root = [1,2,3,4], x = 4, y = 3
Output: false思路：就是level order traverse，BFS，记录一下parent, curNode, Depth;
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {private class Node {public TreeNode parent;public TreeNode curNode;public int depth;public Node(TreeNode parent, TreeNode curNode, int depth) {this.parent = parent;this.curNode = curNode;this.depth = depth;}}public boolean isCousins(TreeNode root, int x, int y) {if(root == null) {return false;}Queue<Node> queue = new LinkedList<Node>();queue.offer(new Node(null, root, 0));Node xNode = new Node(null, null, 0);Node yNode = new Node(null, null, 0);boolean find = false;while(!queue.isEmpty() && !find) {int size = queue.size();while(size > 0) {Node node = queue.poll();size--;if(node.curNode.val == x) {xNode = node;find = true;}if(node.curNode.val == y) {yNode = node;find = true;}if(node.curNode.left != null) {queue.offer(new Node(node.curNode, node.curNode.left, node.depth + 1));}if(node.curNode.right != null) {queue.offer(new Node(node.curNode, node.curNode.right, node.depth + 1));}}}return xNode.parent != yNode.parent && xNode.depth == yNode.depth;}
}思路：更巧妙的是: 判断是否是一个parent下来的，那么直接判断如果有两个children，是否是 x,y即可；其余情况只要在一层find两者就可以了。
/*** 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;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while(!queue.isEmpty()) {int size = queue.size();boolean hasx = false;boolean hasy = false;for(int i = 0; i < size; i++) {TreeNode node = queue.poll();if(node.val == x) {hasx = true;}if(node.val == y) {hasy = true;}if(node.left != null && node.right != null) {if((node.left.val == x && node.right.val == y)|| (node.left.val == y && node.right.val == x)){return false;}}if(node.left != null) {queue.offer(node.left);}if(node.right != null) {queue.offer(node.right);}}if(hasx == true && hasy == true) {return true;}}return false;}
}
这篇关于Cousins in binary tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
