《剑指offer》79--判断是不是平衡二叉树[C++][Java]
2022/1/9 1:03:38
本文主要是介绍《剑指offer》79--判断是不是平衡二叉树[C++][Java],对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
判断是不是平衡二叉树_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目,配有官方题解,在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tags=&title=&difficulty=0&judgeStatus=0&rp=1
题目描述
输入一棵节点数为 n 二叉树,判断该二叉树是否是平衡二叉树。
在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树
平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树;或者它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
样例解释:
样例二叉树如图,为一颗平衡二叉树
注:我们约定空树是平衡二叉树。
数据范围:n \le 100n≤100,树上节点的val值满足 0 \le n \le 10000≤n≤1000
要求:空间复杂度O(1)O(1),时间复杂度 O(n)O(n)
解题思路
【C++解法】
1、前序遍历
从上到下遍历,
借助一个获取树深度的递归函数,根据该结点的左右子树高度差判断是否平衡,然后递归地对左右子树进行判断。在判断上层结点的时候,会多次重复遍历下层结点,增加了不必要的开销。
class Solution { public: bool IsBalanced_Solution(TreeNode* pRoot) { if(pRoot == NULL) {return true;} return abs(getDepth(pRoot->left) - getDepth(pRoot->right)) <= 1 && IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right); } int getDepth(TreeNode* pRoot){ return pRoot ? 1 + max(getDepth(pRoot->left), getDepth(pRoot->right)) : 0; } };
2、后序遍历
从下往上遍历,
如果子树是平衡二叉树,则返回子树的高度;如果发现子树不是平衡二叉树,则直接停止遍历,这样至多只对每个结点访问一次。
两个关键步骤:
1)检查左右子树高度差;
2)判断子树是否为平衡树。
两个返回值,一个return,一个引用。
class Solution { public: bool IsBalanced_Solution(TreeNode* pRoot) { int depth = 0; return isBalanced(pRoot, depth); } bool isBalanced(TreeNode* pRoot, int& depth) { if (pRoot) { int left = 0, right = 0; if (isBalanced(pRoot->left, left) && isBalanced(pRoot->right, right)) { int diff = abs(left - right); if (diff > 1) {return false;} depth = max(left, right) + 1; return true; } else {return false;} } else {return true;} } };
【Java解法】
1、前序遍历
public class Solution { public boolean IsBalanced_Solution(TreeNode root) { if (root == null) {return true;} return Math.abs(dfs(root.left) - dfs(root.right)) <= 1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right); } private int dfs(TreeNode root){ return root == null ? 0 : 1 + Math.max(dfs(root.left), dfs(root.right)); } }
2、后序遍历
public class Solution { public boolean IsBalanced_Solution(TreeNode root) { return dfs(root) == -1 ? false : true; } int dfs(TreeNode root){ if (root == null) {return 0;} int l = dfs(root.left); int r = dfs(root.right); if (l == -1 || r == -1) {return -1;} if (Math.abs(l-r) > 1) {return -1;} return Math.max(l,r) + 1; } }
这篇关于《剑指offer》79--判断是不是平衡二叉树[C++][Java]的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现