X

LEETCODE 993. Cousins in Binary Tree 解题思路分析

题目大意:

二叉树的堂兄弟节点

在二叉树中,根节点位于深度 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

提示:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=993

解题思路分析:

看到二叉树的题目,你应该立刻意识到使用dfs或者bfs来解题。本题也不例外,使用dfs解题会非常方便。

我们从根节点开始向下dfs递归遍历二叉树的每一个节点。dfs函数中,我们需要定义level和parent两个变量来代表当前层以及当前节点的父节点。递归函数中,如果当前节点值等于x,那么我们记录下x所在的level,以及x的父节点。同时结束递归。同理,如果当前节点值等于y,那么我们记录下y所在的level,以及y的父节点。同时结束递归。

另外如果当前节点既不是x也不是y的话,我们继续向下递归,如果当前节点存在右子节点,我们递归至其右子节点,参数level加一,parent节点变为当前节点。同理,如果当前节点存在左子节点,我们递归至其左子节点,参数level加一,parent节点变为当前节点。

所有递归结束后,我们查看x和y的level是否相同,并且他们的父节点是否不同,如果满足上述条件的话,那么返回true,反之返回false。

实现代码:

int xLevel, yLevel;
int xParent, yParent;
public boolean isCousins(TreeNode root, int x, int y) {
    dfs(root,x,y,0,0);
    return xLevel>0&&xLevel==yLevel&&xParent!=yParent;
}

void dfs(TreeNode root, int x, int y, int level, int parent){
    if(root.val==x){
        xLevel=level;
        xParent=parent;
        return;
    }
    if(root.val==y){
        yLevel=level;
        yParent=parent;
        return;
    }
    if(root.left!=null) dfs(root.left,x,y,level+1,root.val);
    if(root.right!=null) dfs(root.right,x,y,level+1,root.val);
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Cousins in Binary Tree.

Memory Usage: 37.1 MB, less than 7.14% of Java online submissions for Cousins in Binary Tree.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-993-cousins-in-binary-tree-解题思路分析/
Categories: leetcode
kwantong: