LeetCode:110_Balanced Binary Tree | 平衡二叉树 | Easy
2023-09-14 09:00:07 时间
要求:判断一棵树是否是平衡二叉树
Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
代码如下:
1 struct TreeNode { 2 int val; 3 TreeNode *left; 4 TreeNode *right; 5 TreeNode(int x): val(x),left(NULL), right(NULL) {} 6 }; 7 8 int maxTreeDepth(TreeNode *root) //先求树的深度 9 { 10 if (NULL == root) 11 return 0; 12 int lval = maxTreeDepth(root->left); 13 int rval = maxTreeDepth(root->right); 14 return 1 + (lval > rval ? lval:rval); 15 } 16 bool isBalanced(TreeNode *root)//根据树的深度再来判断是否是平衡树 17 { 18 if(NULL == root) 19 return true; 20 int diff = maxTreeDepth(root->left) - maxTreeDepth(root->right); 21 if (diff < -1 || diff > 1) 22 return false; 23 return isBalanced(root->left) && isBalanced(root->right); 24 }
相关文章
- [LeetCode] Invert Binary Tree - 二叉树翻转系列问题
- Java实现 LeetCode 834 树中距离之和(DFS+分析)
- Java实现 LeetCode 823 带因子的二叉树(DP)
- Java实现 LeetCode 617 合并二叉树(遍历树)
- Java实现 LeetCode 334 递增的三元子序列
- Java实现 LeetCode 236 二叉树的最近公共祖先
- Java实现 LeetCode 104 二叉树的最大深度
- Java实现 LeetCode 94 二叉树的中序遍历
- 【二叉树】LeetCode 114. 二叉树展开为链表【中等】
- LeetCode:114_Flatten Binary Tree to Linked List | 将一棵二叉树变成链表的形式 | Medium
- LeetCode: 106_Construct Binary Tree from Inorder and Postorder Traversal | 根据中序和后序遍历构建二叉树 | Medium
- (LeetCode 203)Remove Linked List Elements
- [LeetCode] 108. Convert Sorted Array to Binary Search Tree ☆(升序数组转换成一个平衡二叉树)
- [LeetCode] 111. Minimum Depth of Binary Tree ☆(二叉树的最小深度)
- [LeetCode] 104. Maximum Depth of Binary Tree ☆(二叉树的最大深度)
- leetcode 415. 字符串相加 js 实现
- LeetCode之Balanced Binary Tree 平衡二叉树
- 【LeetCode】543. 二叉树的直径
- 【LeetCode】876.链表的中间节点