Hello, 大家好，今天是我参加8月更文的第 15 天，今天给大家带来的关于二叉树相关的算法题是求二叉树的堂兄弟节点，正文如下：

题目

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

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

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

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

示例1

示例2

示例3

解题思路

根据题意，要判断 x, y 是否是堂兄弟，我们首先就需要算出 x 和 y 的深度以及父节点。

因此，我们可以从根节点开始，近行一次深度优先搜索，在遍历的过程中记录深度以及父节点。

当遍历到这俩个节点的时候，就可以判断它们俩是否是堂兄弟节点。

遍历三部曲

代码实现

/**
 * 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 TreeNode xParent;
    public int xDepth;
    public int x;
    public boolean xFound;

    public TreeNode yParent;
    public int yDepth;
    public int y;
    public boolean yFound;

    public boolean isCousins(TreeNode root, int x, int y) {
        this.x = x;
        this.y = y;
        DFS(root, 0, null);
        return xDepth == yDepth && xParent != yParent;
    }

    public void DFS(TreeNode r, int level, TreeNode parent){
        if (r == null) {
            return;
        }

        if (r.val == x) {
            xParent = parent;
            xDepth = level;
            xFound = true;
        } else if (r.val == y){
            yParent = parent;
            yDepth = level;
            yFound = true;
        }

        if (xFound && yFound) {
            return;
        }

        DFS(r.left, level+1, r);
        DFS(r.right, level+1, r);
    }
}

最后

复杂度分析：

• 时间复杂度：O(n)，其中 n 是树中的节点个数。在最坏情况下，我们需要遍历整棵树，时间复杂度为 O(n)。

• 空间复杂度：O(n)，即为深度优先搜索的过程中需要使用的栈空间。在最坏情况下，树呈现链状结构，递归的深度为 O(n)。