110 Balanced Binary Tree - Algorithm Practice

Algorithm Practice

Search…

Algorithm Practice

94 Binary Tree Inorder Traversal

114 Flatten Binary Tree to Linked List

116 Populating Next Right Pointers in Each Node

117 Populating Next Right Pointers in Each Node II

124 Binary Tree Maximum Path Sum

144 Binary Tree Preorder Traversal

145 Binary Tree Postorder Traversal

366 Find Leaves of Binary Tree

257 Binary Tree Paths

235 Lowest Common Ancestor of a Binary Search Tree

236 Lowest Common Ancestor of a Binary Tree

671 Second Minimum Node In a Binary Tree

662 Maximum Width of Binary Tree

101 Symmetric Tree

102 Binary Tree Level Order Traversal

103 Binary Tree Zigzag Level Order Traversal

104 Maximum Depth of Binary Tree

107 Binary Tree Level Order Traversal II

108 Convert Sorted Array to Binary Search Tree

110 Balanced Binary Tree

111 Minimum Depth of Binary Tree

113 Path Sum II

623 Add One Row to Tree

222 Count Complete Tree Nodes

450 Delete Node in a BST

156 Binary Tree Upside Down

536 Construct Binary Tree from String

543 Diameter of Binary Tree

545 Boundary of Binary Tree

105 Construct Binary Tree from Preorder and Inorder Traversal

106 Construct Binary Tree from Inorder and Postorder Traversal

606 Construct String from Binary Tree

655 Print Binary Tree

742 Closest Leaf in a Binary Tree

783 Minimum Distance Between BST Nodes

Topological Sort

Breadth First Search

Dynamic Programming

Reservoir Sampling

Powered By GitBook

110 Balanced Binary Tree

110. Balanced Binary Tree
1. Question
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 ofeverynode never differ by more than 1.
2. Implementation
(1) DFS
1
class Solution {
2
    public boolean isBalanced(TreeNode root) {
3
        if (root == null) {
4
            return true;
5
        }
6
​
7
        return dfs(root) != -1;
8
    }
9
​
10
    public int dfs(TreeNode node) {
11
        if (node == null) {
12
            return 0;
13
        }
14
​
15
        int leftHeight = dfs(node.left);
16
        int rightHeight = dfs(node.right);
17
​
18
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
19
            return -1;
20
        }
21
        return Math.max(leftHeight, rightHeight) + 1;
22
    }
23
}
Copied!
3. Time & Space Complexity
DFS: 时间复杂度: O(n), 空间复杂度: O(h)

108 Convert Sorted Array to Binary Search Tree

111 Minimum Depth of Binary Tree

Last modified 2yr ago

Copy link

Contents

110. Balanced Binary Tree

2. Implementation

3. Time & Space Complexity