【LeetCode】993. 二叉树的堂兄弟节点（Java）

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。

提示：

二叉树的节点数介于 2 到 100 之间。每个节点的值都是唯一的、范围为 1 到 100 的整数。

解法一

队列

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isCousins(TreeNode root, int x, int y) { //队列 Queue<TreeNode> queue = new LinkedList<>(); //offer()方法的作用和add()的作用一样，不过如果add添加失败是报错，而offer是返回false queue.offer(root); while (!queue.isEmpty()) { //x和y是否在当前层的标识，当前层结束遍历后，如果两个都为真，那么是堂兄弟节点 //如果都不为真，那么还没找到，如果只有一个为真，那么就不会是堂兄弟节点 boolean xFlag = false, yFlag = false; //遍历当前层的数据 int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode tree = queue.poll(); //特判（判断当前节点的左右子节点是否符合x和y，如果符合，返回false） if ((tree.left != null && tree.right != null) && ((tree.left.val == x && tree.right.val == y) || (tree.left.val == y && tree.right.val == x))) return false; //把当前节点的只有子树放到队列中 if (tree.left != null) queue.offer(tree.left); if (tree.right != null) queue.offer(tree.right); //如果在当前层找到，把对应的标识改为true if (tree.val == x) xFlag = true; else if (tree.val == y) yFlag = true; //如果两个都为true，说明两个都在同一层，返回true if (xFlag && yFlag) return true; } //当前循环结束后，如果只有一个为真，返回false if ((xFlag && !yFlag) || (!xFlag && yFlag)) return false; //如果两个都为false，那就继续循环，直到遍历所有的节点 } return false; } }

解法二

递归

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private TreeNode[] preTree = new TreeNode[2]; //x和y的父节点 private int[] index = new int[2]; //x和y的下标 public boolean isCousins(TreeNode root, int x, int y) { //递归 func(root, null, 1, x); func(root, null, 1, y); return index[0] == index[1] && preTree[0] != preTree[1]; } private void func(TreeNode tree, TreeNode pre, int depth, int target) { if (tree == null) return; if (tree.val == target) { if (index[0] == 0) { index[0] = depth; preTree[0] = pre; } else { index[1] = depth; preTree[1] = pre; } } else { func(tree.left, tree, depth + 1, target); func(tree.right, tree, depth + 1, target); } } }