手撸二叉树之二叉树的堂兄弟节点

题目

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

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

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

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

示例1

示例2

示例3

解题思路

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

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

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

遍历三部曲

1. 确定递归函数的参数和返回值：
   函数的参数为传入的节点，维护的深度以及维护的父节点；因为要遍历整棵二叉树，所以不需要有返回值；
2. 确定递归函数的终止条件：
   当俩个节点都找到时，则返回或者当 root 为 null 时返回；
3. 确定递归函数的单层逻辑：
   遍历如果遇到 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)。