110. Balanced Binary Tree
Tree Binary 110 Balanced
2023-09-11 14:14:21 时间
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.
Example 1:
Given the following tree [3,9,20,null,null,15,7]
:
3 / \ 9 20 / \ 15 7
Return true.
Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]
:
1 / \ 2 2 / \ 3 3 / \ 4 4
平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
public bool IsBalanced(TreeNode root) { if (root == null) { return true; } int maxLeftDepth = MaxDepth(root.left); int maxRightDepth = MaxDepth(root.right); bool flag1 = Math.Abs(maxLeftDepth - maxRightDepth) <= 1; bool flag2 = IsBalanced(root.left); bool flag3 = IsBalanced(root.right); return flag1 && flag2 && flag3; } public int MaxDepth(TreeNode root) { int depth; if (root == null) { depth = 0; } else { depth = 1; TreeNode left = root.left; TreeNode right = root.right; if (left != null || right != null) { int leftDepth = MaxDepth(left); int rightDepth = MaxDepth(right); depth = depth + Math.Max(leftDepth, rightDepth); } } return depth; }
相关文章
- Leetcode: Closest Binary Search Tree Value
- HDU 1710 Binary Tree Traversals(二叉树)
- 235. Lowest Common Ancestor of a Binary Search Tree
- 【BZOJ2648】SJY摆棋子(KD-Tree)
- 【BZOJ2588】Count On a Tree(主席树)
- BZOJ 2631 tree 动态树(Link-Cut-Tree)
- 【BZOJ2654】tree 二分+最小生成树
- 【BZOJ3489】A simple rmq problem kd-tree
- BNUOJ 13358 Binary Apple Tree
- 查找树-- Binary Search Tree 【二叉查找树】原理图解及示例代码
- [LeetCode] Binary Tree Right Side View
- [LeetCode] Binary Tree Maximum Path Sum
- [LeetCode] Binary Tree Level Order Traversal II
- [LeetCode] Maximum Depth of Binary Tree
- poj 3321 Apple Tree(分块大法)
- Couldnt check the working tree for unmerged files because of an error. bad signature index file cor
- 看动画学算法之:平衡二叉搜索树AVL Tree
- 【LeetCode】226. Invert Binary Tree
- 【LeetCode】173. Binary Search Tree Iterator (2 solutions)
- 【LeetCode】94. Binary Tree Inorder Traversal (3 solutions)
- 【LeetCode】108. Convert Sorted Array to Binary Search Tree
- 【LeetCode】124. Binary Tree Maximum Path Sum
- LeetCode:Balanced Binary Tree
- [LeetCode] 1261. Find Elements in a Contaminated Binary Tree 在受污染的二叉树中查找元素
- [LeetCode] 993. Cousins in Binary Tree 二叉树的表兄弟节点
- [LeetCode] 979. Distribute Coins in Binary Tree 在二叉树中分配硬币
- [LeetCode] 968. Binary Tree Cameras 二叉树相机
- [LeetCode] 261. Graph Valid Tree 图验证树
- [LintCode] Invert Binary Tree 翻转二叉树
- [LeetCode] 111. Minimum Depth of Binary Tree 二叉树的最小深度
- Validate Binary Search Tree