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

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

今天给大家带来的关于二叉树相关的算法题是求二叉树的堂兄弟节点，正文如下：

题目

在二叉树中，根节点位于深度 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 { this.x = x; this.y = y; DFS(root, 0, null); return xDepth == yDepth && xParent != yParent; } public void DFS(TreeNode r, int{ 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)。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。