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

HelloWorld杰少

关注

发布于: 4 小时前

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

题目

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

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

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

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

示例 1

示例 2

示例 3

解题思路

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

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

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

遍历三部曲

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

发布于: 4 小时前阅读数: 2

原文链接:【http://xie.infoq.cn/article/6f621f28dcd2c7ca424d554a3】。文章转载请联系作者。

HelloWorld杰少

关注

佛系编码 2019.05.13 加入

红鲤鱼与绿鲤鱼与驴。

发布

暂无评论

创作场景

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

题目

解题思路

代码实现

最后

HelloWorld杰少

评论