Balanced binary tree topic¶
There are still some questions about balancing binary trees in Likou, and they are all very classic. I recommend everyone to practice. Today I have selected 4 questions for everyone. If you thoroughly understand these questions, you should not lose your thoughts when you encounter other balanced binary tree questions. After you understand my ideas, I suggest you find a few more topics to practice your hands and consolidate your learning results.
110. Balanced binary tree (simple)¶
The easiest way is to judge whether a tree is a balanced binary tree, let's take a look.
Title description¶
Given a binary tree, judge whether it is a highly balanced binary tree.
In this question, a highly balanced binary tree is defined as:
The absolute value of the height difference between the left and right subtrees of each node of a binary tree does not exceed 1.
Example 1:
Given a binary tree [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
Return true.
Example 2:
Given a binary tree [1,2,2,3,3,null,null,4,4]
1
/ \
twenty two
/ \
3 3
/ \
4 4
Return false
Ideas¶
Since a balanced binary tree is defined as ** the absolute value of the height difference between the left and right subtrees of each node of a binary tree does not exceed 1. **Described in pseudo code is:
if abs(height(root.left)-height(root.right)) <= 1 and root.left is also a balanced binary tree and root.right is also a balanced binary tree:
print('is a balanced binary tree')
else:
print('Not a balanced binary tree')
And root.left and root.right how to judge whether it is a binary balanced tree is the same as root, it can be seen that this problem is obviously recursive.
So we first need to know how to calculate the height of a subtree. This can be easily calculated recursively. The Python code for calculating the height of the subtree is as follows:
def dfs(node, depth):
if not node: return 0
l = dfs(node.left, depth + 1)
r = dfs(node.right, depth + 1)
return max(l, r) + 1
Code¶
Code support: Python3
Python3 Code:
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def dfs(node, depth):
if not node: return 0
l = dfs(node.left, depth + 1)
r = dfs(node.right, depth + 1)
return max(l, r) + 1
if not root: return True
if abs(dfs(root.left, 0)-dfs(root.right, 0))> 1: return False
return self.isBalanced(root.left) and self.isBalanced(root.right)
Complexity Analysis
-Time complexity: For isBalanced, since each node is visited at most once, the time complexity of this part is \(O(N)\), and the number of times the dfs function is called each time does not exceed \(log N\), so The total time complexity is \(O(NlogN)\), where \(N\) is the total number of nodes in the tree. -Space complexity: Due to the use of recursion, the bottleneck of the space complexity here is the stack space, so the space complexity is \(O(h)\), where \(h\) is the height of the tree.
108. Convert an ordered array to a binary search tree (simple)¶
108 and 109 are basically the same, but the data structure is different, 109 becomes a linked list. Because linked list operations need to consider more factors than arrays, 109 is a medium level of difficulty.
Title description¶
Convert an ordered array in ascending order into a highly balanced binary search tree.
In this question, a highly balanced binary tree means that the absolute value of the height difference between the left and right subtrees of each node of a binary tree does not exceed 1.
Example:
Given an ordered array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which can represent the following highly balanced binary search tree:
0
/ \
-3 9
/ /
-10 5
Ideas¶
For this problem or given a binary search tree, change it to balanced (to be discussed later) The basic idea is the same.
The requirement of the question is to transform the ordered array into:
- Highly balanced binary tree
- Binary search tree
Because the balanced binary tree is that the absolute value of the height difference between the left and right subtrees does not exceed 1. Therefore, a simple method is to select the midpoint as the root node, the left subtree of the root node as the left subtree, and the right subtree as the right subtree. **The reason is very simple. This allocation can ensure that the number of nodes in the left and right subtrees does not exceed one. Therefore, the height difference will naturally not exceed 1.
The above operation also satisfies the binary search tree, because the array given by the title is ordered.
You can also choose another number as the root node instead of the midpoint, which also shows that the answer is not unique.
Code¶
Code support: Python3
Python3 Code:
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums: return None
mid = (len(nums)-1) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid + 1:])
return root
Complexity Analysis
-Time complexity: Since each node can be visited at most once, the total time complexity is \(O(N)\), where \(N\) is the length of the array. -Space complexity: Due to the use of recursion, the bottleneck of the space complexity here is the stack space, so the space complexity is \(O(h)\), where \(h\) is the height of the tree. At the same time, since it is a balanced binary tree, \(h\) is \(log N\).
109. Ordered linked list conversion binary search tree (medium)¶
Title description¶
`Given a singly linked list, the elements in it are sorted in ascending order and converted into a highly balanced binary search tree.
In this question, a highly balanced binary tree means that the absolute value of the height difference between the left and right subtrees of each node of a binary tree does not exceed 1.
Example:
Given an ordered linked list: [-10, -3, 0, 5, 9],
A possible answer is: [0, -3, 9, -10, null, 5], which can represent the following highly balanced binary search tree:
0
/ \
-3 9
/ /
-10 5
Ideas¶
Same idea as 108. The difference is the difference in the data structure, so we need to pay attention to the difference in the operation of the linked list and the array.
(In the case of an array)
Let's look at the next linked list:
(In the case of a linked list)
To find the midpoint, just use the classic fast and slow pointers. At the same time, in order to prevent the appearance of the ring, we need to cut off the next pointer to mid, so we need to record a node before the midpoint, which only needs to be recorded with a variable pre.
Code¶
Code support: Python3
Python3 Code:
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
if not head:
return head
pre, slow, fast = None, head, head
while fast and fast.next:
fast = fast.next.next
pre = slow
slow = slow.next
if pre:
pre.next = None
node = TreeNode(slow.val)
if slow == fast:
return node
node.left = self.sortedListToBST(head)
node.right = self.sortedListToBST(slow.next)
return node
Complexity Analysis
-Time complexity: Since each node can be visited at most once, the total time complexity is \(O(N)\), where \(N\) is the length of the linked list. -Space complexity: Due to the use of recursion, the bottleneck of the space complexity here is the stack space, so the space complexity is \(O(h)\), where \(h\) is the height of the tree. At the same time, since it is a balanced binary tree, \(h\) is \(log N\).
1382. Balance the binary search tree (medium)¶
Title description¶
Give you a binary search tree, please return a balanced binary search tree. The newly generated tree should have the same node value as the original tree.
If the height difference between the two subtrees of each node in a binary search tree does not exceed 1, we call the binary search tree balanced.
If there are multiple construction methods, please return any one.
Example:
Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also a feasible construction solution.
prompt:
The number of tree nodes is between 1 and 10^4.
The values of tree nodes are different from each other and are between 1 and 10^5.
Ideas¶
Since the middle-order traversal of the binary search tree is an ordered array, the problem can easily be transformed into 108. Convert the ordered array to a binary search tree (simple).
Code¶
Code support: Python3
Python3 Code:
class Solution:
def inorder(self, node):
if not node: return []
return self.inorder(node.left) + [node.val] + self.inorder(node.right)
def balanceBST(self, root: TreeNode) -> TreeNode:
nums = self.inorder(root)
def dfs(start, end):
if start == end: return TreeNode(nums[start])
if start> end: return None
mid = (start + end) // 2
root = TreeNode(nums[mid])
root.left = dfs(start, mid-1)
root.right = dfs(mid + 1, end)
return root
return dfs(0, len(nums)-1)
Complexity Analysis
-Time complexity: Since each node can be visited at most once, the total time complexity is \(O(N)\), where \(N\) is the length of the linked list. -Space complexity: Although recursion is used, the bottleneck is not in the stack space, but a nums array with a length of \(N\), so the space complexity is \(O(N)\), where \(N\) is the total number of nodes in the tree .
to sum up¶
This article uses four questions about binary balanced trees to help you identify the thinking logic behind this type of problem. Let's summarize the knowledge learned.
A balanced binary tree refers to: The absolute value of the height difference between the left and right subtrees of each node of a binary tree does not exceed 1.
If you need to let you judge whether a tree is a balanced binary tree, just deadlock the definition, and then use recursion to easily solve it.
If you need to convert an array or linked list (logically linear data structure) into a balanced binary tree, you only need to select a node at random, and allocate half to the left subtree and the other half to the right subtree.
At the same time, if you are required to transform into a balanced binary search tree, you can choose the midpoint of the sorted array (or linked list), where the element on the left is the left subtree, and the element on the right is the right subtree.
Tip 1: If you don't need a binary search tree, you don't need to sort, otherwise you need to sort.
Tip 2: You can also choose not to choose the midpoint, the algorithm needs to be adjusted accordingly, and interested students can try it.
Tip 3: The operation of the linked list requires special attention to the existence of rings.
For more solutions, please visit my LeetCode solution repository: https://github.com/azl397985856/leetcode. Currently it has 37K stars.
Pay attention to the official account and try to restore the problem-solving ideas in clear and straightforward language, and there are a lot of illustrations to teach you to identify routines and to efficiently solve the problems.