2021-06-20

leetCode

二叉树

二叉树的堂兄弟节点

题目

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

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

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

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

输入： root = [1,2,3,4] x = 4, y = 3

输出： false

输入：root = [1,2,3,null,4,null,5], x = 5, y = 4

输出：true

分析

要看 x，y 是不是堂兄弟节点，要看他们的深度是不是一样，以及他们的父节点是不是不一样的。

那么我们要定义一个全局的变量来记录每个节点的深度和父节点。这样在找到 x，y 之后，拿 xDepth和xParent比较一下就知道是不是堂兄弟了。

class Solution {

   //先在类中声明全局变量

    int xparent, xdepth, yparent,ydepth;

   public boolean isCousins(TreeNode root, int x, int y) {

       dfs(root.left, 1, x, y, root.val);

       dfs(root.right, 1, x, y, root.val);

       return (xparent != yparent) && (xdepth == ydepth);

   }

   public void dfs(TreeNode node, int dep, int x, int y, int par) {

       if (node == null) {

           return;

       }

       if (node.val == x) {

           xparent = par;

           xdepth = dep;

       } else if (node.val == y) {

           yparent = par;

           ydepth = dep;

       } else {

           dfs(node.left, dep+1, x, y, node.val);

           dfs(node.right, dep+1, x, y, node.val);

       }

   }

}