写点什么

【LeetCode】二叉树的堂兄弟节点 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 05 月 17 日

题目描述

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


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


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


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


示例 1:

输入:root = [1,2,3,4], x = 4, y = 3输出:false
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/cousins-in-binary-tree著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 这个题目题意容易理解。属于树的基本操作。可以采用 DFS 或者 BFS 解决。

  • 采用 BFS 的时候,要注意每层的节点数,当遍历完成本层的节点数之后,在进行下一层节点便利,层数加一。

代码

/** * 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) {        Deque<TreeNode> deque = new ArrayDeque<>();        deque.offer(root);        int level = 0;        int xParent = 0;        int xLevel = 0;        int yParent = 0;        int yLevel = 0;        while (!deque.isEmpty()) {            int size = deque.size();            for (int i = 0; i < size; i++) {                TreeNode node = deque.poll();                if (node.left != null) {                    if (node.left.val == x) {                        xParent = node.val;                        xLevel = level + 1;                    }                    if (node.left.val == y) {                        yParent = node.val;                        yLevel = level + 1;                    }                    deque.offer(node.left);                }                if (node.right != null) {                    if (node.right.val == x) {                        xParent = node.val;                        xLevel = level + 1;                    }                    if (node.right.val == y) {                        yParent = node.val;                        yLevel = level + 1;                    }                    deque.offer(node.right);                }            }            level++;        }        if (xLevel == yLevel && xParent != yParent) {            return true;        }        return false;    }}
复制代码

总结

  • 算法的时间复杂度是 O(n), 空间复杂度是 O(n)

  • 坚持每日一题,加油!

发布于: 2021 年 05 月 17 日阅读数: 11
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】二叉树的堂兄弟节点Java题解