二叉树的堂兄弟节点

说在前面

🎈今天给大家带来的是算法练习,题目为二叉树的堂兄弟节点。

题目描述

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。\
如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。\
我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。\
只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。\
示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

思路分析

题目要我们求的是二叉树的堂兄弟节点，那么我们首先就要来了解一下什么是堂兄弟节点，简单来说，就是父亲不同但是树节点的深度又是相同的，那么他们就是一对堂兄弟节点，所以我们只要按照题意来，找出两个节点的父节点和节点深度并进行比较即可。这种题目我们可以使用深度优先搜索来进行解题，具体步骤如下：

以下几种情况要注意剪枝

• （1）已经找到两个节点；
• （2）已经找到第一个节点并且当前遍历深度大于第一个节点深度。

AC代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} x
 * @param {number} y
 * @return {boolean}
 */
var isCousins = function(root, x, y) {
    let pre1 = '',floor1 = Infinity,res = '';
    const compare = function(r,floor,pre){
        if(r.val == x || r.val == y){
            if(floor1 == Infinity){
                floor1 = floor;
                pre1 = pre;
            }else{
                res = (floor1 == floor && pre1 != pre);
            }
            return true;
        }
        return false;
    }
    const dfs = function(r,floor = 0,pre = null){
        if(!r || res != '' || r.val == pre1 || floor > floor1) return;
        if(compare(r,floor,pre)) return;
        dfs(r.left,floor + 1,r.val);
        dfs(r.right,floor + 1,r.val);
    }
    dfs(root);
    return res;
};

说在后面

🎉这里是JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。