网站针对爬虫爬取做的优化,html代码特效,个人业务网站源码php,wordpress分块标签
树深度优先搜索递归
题目描述
给定一个二叉树#xff0c;判断它是否是高度平衡的二叉树。
本题中#xff0c;一棵高度平衡的二叉树定义为#xff1a; 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。 原题#xff1a;LeetCode 110.平衡二叉树
思路及…标签
树深度优先搜索递归
题目描述
给定一个二叉树判断它是否是高度平衡的二叉树。
本题中一棵高度平衡的二叉树定义为 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。 原题LeetCode 110.平衡二叉树
思路及实现
方法一自顶向下递归纯递归
思路
定义函数 height\texttt{height}height用于计算二叉树中的任意一个节点 ppp 的高度 为了判断二叉树是否平衡我们可以采用一个自顶向下的递归方法。该方法通过计算每个节点左右子树的高度差并与 1 进行比较来判断当前子树是否平衡。如果当前子树平衡则继续递归检查其子节点。
代码实现
Java版本
class Solution { // 判断二叉树是否平衡 public boolean isBalanced(TreeNode root) { // 如果根节点为空即树为空则树是平衡的 if (root null) { return true; } // 否则判断当前节点的左右子树高度差是否不超过1并且左右子树都是平衡的 else { return Math.abs(height(root.left) - height(root.right)) 1 isBalanced(root.left) // 递归判断左子树是否平衡 isBalanced(root.right); // 递归判断右子树是否平衡 } } // 计算树的高度 public int height(TreeNode root) { // 如果根节点为空即树为空或到达叶子节点的下一层则返回高度为0 if (root null) { return 0; } // 否则返回当前节点左子树和右子树中的较大高度加1当前节点的高度为其子树的最大高度加1 else { return Math.max(height(root.left), height(root.right)) 1; } } // TreeNode类假设已经在外部定义 // class TreeNode { // int Val; // TreeNode Left; // TreeNode Right; // TreeNode(int val) { Val val; } // } }说明isBalanced 方法检查树是否平衡同时递归地计算左右子树的高度。height 方法返回树的高度。 C语言版本
int height(struct TreeNode* root) {if (root NULL) {return 0;} else {return fmax(height(root-left), height(root-right)) 1;}
}bool isBalanced(struct TreeNode* root) {if (root NULL) {return true;} else {return fabs(height(root-left) - height(root-right)) 1 isBalanced(root-left) isBalanced(root-right);}
}说明在C语言中我们使用了fmax函数来计算两个整数中的较大值并且fabs函数用于计算绝对值。 Python3版本
class Solution:def isBalanced(self, root: TreeNode) - bool:def height(root: TreeNode) - int:if not root:return 0return max(height(root.left), height(root.right)) 1if not root:return Truereturn abs(height(root.left) - height(root.right)) 1 and self.isBalanced(root.left) and self.isBalanced(root.right) 说明在Python中我们约定如果子树不平衡则height函数返回-1这样可以在isBalanced中直接利用返回值进行判断。 Golang版本
package mainimport (math
)func isBalanced(root *TreeNode) bool {if root nil {return true}return abs(height(root.Left) - height(root.Right)) 1 isBalanced(root.Left) isBalanced(root.Right)
}func height(root *TreeNode) int {if root nil {return 0}return max(height(root.Left), height(root.Right)) 1
}func max(x, y int) int {if x y {return x}return y
}func abs(x int) int {if x 0 {return -1 * x}return x
}作者力扣官方题解
链接https://leetcode.cn/problems/balanced-binary-tree/solutions/377216/ping-heng-er-cha-shu-by-leetcode-solution/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。说明在Golang版本中我们使用了一个辅助函数dfs来进行深度优先搜索该函数返回子树的高度和是否平衡两个值。如果子树不平衡则dfs返回-1和false。abs和max是辅助函数分别用于计算绝对值和取两个整数中的较大值。 复杂度分析 时间复杂度 时间复杂度为 O(n)其中 n 是二叉树中的节点数。这是因为在递归的过程中我们需要访问每一个节点来计算其左右子树的高度并且对每个节点都要执行一次判断是否平衡的操作比较高度差以及递归检查子树是否平衡。每个节点最多被访问一次因此总的时间复杂度是线性的。 空间复杂度 空间复杂度取决于递归调用的深度也就是树的深度。在最坏的情况下当树完全不平衡时例如每个节点都只有左子节点或右子节点递归的深度会达到树的高度也就是 O(n)。此时递归调用栈需要存储 O(n) 个节点信息。
然而在平均情况下二叉树是平衡的其深度通常是对数级别的即 O(log n)。因此在平均情况下空间复杂度是 O(log n)。
但需要注意的是空间复杂度并不只包括递归调用栈的开销还包括系统为函数调用分配的其他资源如局部变量等。但在判断二叉树是否平衡的问题中这些开销通常相对较小可以忽略不计。
总结 时间复杂度O(n) 空间复杂度最坏情况O(n) 空间复杂度平均情况O(log n) 其中n 是二叉树中的节点数。
方法一自顶向下递归带后序遍历
思路
方法一由于是自顶向下递归因此对于同一个节点函数 height 会被重复调用导致时间复杂度较高。如果使用自底向上的做法则对于每个节点函数 height 只会被调用一次。
自底向上递归的做法类似于后序遍历对于当前遍历到的节点先递归地判断其左右子树是否平衡再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的则返回其高度高度一定是非负整数否则返回 −1-1−1。如果存在一棵子树不平衡则整个二叉树一定不平衡。
方式二带后序遍历的递归方法自底向上
思路
带后序遍历的递归方法自底向上在遍历到每个节点时首先递归地检查其左右子树是否平衡并返回子树的高度。如果子树不平衡即高度差大于1则立即返回-1表示不平衡并向上传递这个信息。如果子树平衡则返回其高度继续向上传递。这样在遍历到根节点时就可以知道整棵树是否平衡。
代码实现
Java版本
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val x; }
}public class Solution {public boolean isBalanced(TreeNode root) {return height(root) ! -1;}private int height(TreeNode node) {if (node null) {return 0;}int leftHeight height(node.left);if (leftHeight -1) {return -1;}int rightHeight height(node.right);if (rightHeight -1) {return -1;}if (Math.abs(leftHeight - rightHeight) 1) {return -1;}return Math.max(leftHeight, rightHeight) 1;}
}说明在Java版本中isBalanced方法调用height方法来判断树是否平衡。height方法递归地计算每个节点的高度并在发现不平衡时返回-1。 C语言版本
#include limits.htypedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;int height(TreeNode* node) {if (node NULL) {return 0;}int leftHeight height(node-left);if (leftHeight -1) {return -1;}int rightHeight height(node-right);if (rightHeight -1) {return -1;}if (abs(leftHeight - rightHeight) 1) {return -1;}return MAX(leftHeight, rightHeight) 1;
}bool isBalanced(TreeNode* root) {return height(root) ! -1;
}说明在C语言版本中同样使用height函数来计算节点高度并判断平衡性。注意这里使用了limits.h中的INT_MIN来表示-1的整数类型但在这个例子中我们直接返回-1以及自定义的MAX宏来获取两个数中的较大值或者可以使用#include stdlib.h中的max函数如果存在的话。 Python3版本
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef isBalanced(root):def height(node):if not node:return 0leftHeight height(node.left)if leftHeight -1:return -1rightHeight height(node.right)if rightHeight -1:return -1if abs(leftHeight - rightHeight) 1:return -1return max(leftHeight, rightHeight) 1return height(root) ! -1说明在Python3版本中我们定义了一个嵌套函数height来计算节点高度并在isBalanced函数中调用它。Python中没有类型定义所以我们直接使用类定义来创建树节点。 Golang版本
package main import ( fmt math
) type TreeNode struct { Val int Left *TreeNode Right *TreeNode
} func isBalanced(root *TreeNode) bool { return height(root) ! -1
} func height(node *TreeNode) int { if node nil { return 0 } leftHeight : height(node.Left) if leftHeight -1 { return -1 } rightHeight : height(node.Right) if rightHeight -1 { return -1 } if math.Abs(float64(leftHeight-rightHeight)) 1 { return -1 } return int(math.Max(float64(leftHeight), float64(rightHeight))) 1
}
复杂度分析
时间复杂度O(n)其中n是二叉树中的节点数。每个节点最多被访问一次因此总的时间复杂度是线性的。空间复杂度O(h)其中h是二叉树的高度。这是由递归调用栈的深度决定的。在最坏的情况下树完全不平衡空间复杂度为O(n)。然而在平均情况下二叉树是平衡的其高度通常是对数级别的即O(log n)。但需要注意的是这里的空间复杂度不包括可能由操作系统分配的系统
总结
针对上面提到的自顶向下递归方式一和自底向上递归方式二的二叉树平衡性检查方法我们可以进行如下总结
方式优点缺点时间复杂度空间复杂度方式一自顶向下递归直观易理解直接根据定义判断可能产生大量重复计算效率较低O(n)O(h)h为树的高度最坏情况下为O(n)方式二自底向上递归利用后序遍历减少重复计算效率高依赖于递归和高度差的比较可能难以理解O(n)O(h)h为树的高度最坏情况下为O(n)
注意在方式二中虽然空间复杂度在最坏情况下为O(n)但这是因为递归调用栈的深度可能达到n。在平均情况下对于平衡树空间复杂度为O(log n)。
相似题目
以下是一些与判断二叉树平衡性相关的相似题目它们涉及树的遍历、深度或高度的计算等概念
相似题目难度链接LeetCode 104 二叉树的最大深度简单LeetCode-104LeetCode 110 平衡二叉树简单LeetCode-110LeetCode 111 二叉树的最小深度简单LeetCode-111LeetCode 543 二叉树的直径简单LeetCode-543LeetCode 124 二叉树中的最大路径和困难LeetCode-124
这些题目都涉及到对二叉树的遍历和深度/高度的计算可以通过递归或迭代的方式解决。其中LeetCode 110题目与本文讨论的二叉树平衡性检查最为相似。
