“This is the 8th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”
Flip the binary tree
Flip a binary tree.
Train of thought
Switch the left and right children at each node.
The code is as follows:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
returnroot; }}Copy the codeTime complexity: O(N), where N is the number of nodes in the binary tree.
Space complexity: O(N).
Construct a binary tree
Binary tree brush summary: binary tree traversal
The largest binary tree
Given an array of integers with no repeating elements. A maximum binary tree constructed from this array is defined as follows:
The root of a binary tree is the largest element in the array. The left subtree is the largest binary tree constructed from the left of the largest value in the array. The right subtree is the largest binary tree constructed from the right part of the maximum value in the array. Build the maximum binary tree from the given array and print the root node of the tree.
Train of thought
To construct a tree, we usually construct it in the way of pre-order traversal, because pre-order traversal constructs the middle node first, and then recursively constructs the left and right subtrees.
So, the recursive idea is as follows:
- Recursive parameter and return value: the passed parameter is an array of elements, and the return value is a pointer to the binary root node;
- The terminating condition is: if there is only one element in the array, the current element is a leaf node, then we define a new node for this element, and return;
- To determine the single-layer recursive logic, the work to be processed here is divided into three steps: first find the maximum value and subscript in the array, build the root node, then build the left subtree according to the subscript, and finally build the right subtree;
The code is as follows:
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
TreeNode node = new TreeNode(0);
// When only one element is encountered, it represents a leaf node
if (nums.length == 1){
node.val = nums[0];
return node;
}
// Intermediate node
int maxIndex = getMax(nums);
node.val = nums[maxIndex];
// If there is a left subtree, generate a left subtree,
if (maxIndex > 0) {int[] leftNum = Arrays.copyOfRange(nums, 0, maxIndex);
node.left = constructMaximumBinaryTree(leftNum);
}
// If there is a right subtree, generate a right subtree
if (maxIndex < nums.length - 1) {
int[] right = Arrays.copyOfRange(nums, maxIndex+1, nums.length);
node.right = constructMaximumBinaryTree(right);
}
return node;
}
public int getMax(int[] nums){
int maxIndex = 0;
for (int i = 0; i < nums.length; i++){
if (nums[i] > nums[maxIndex]) maxIndex = i;
}
returnmaxIndex; }}Copy the codeThe above code is redundant and the execution efficiency is very low, as shown below:
So, we can optimize it once. In the above idea, we need to open up the array space of the left and right subtrees each time. We can optimize it at this step by operating directly on the original array with the array subscript index instead of defining a new array with each partition.
The code is as follows:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return construct(nums, 0, nums.length);
}
public TreeNode construct(int[] nums, int l, int r){
if (l == r) return null;
int max_i = max(nums, l, r);
TreeNode node = new TreeNode(nums[max_i]);
node.left = construct(nums, l, max_i);
node.right = construct(nums, max_i+1, r);
return node;
}
public int max(int[] nums, int l, int r){
int max_i = l;
for (int i = l; i < r; i++) {
if(nums[max_i] < nums[i]){ max_i = i; }}returnmax_i; }}Copy the codeSo the execution efficiency is very high.
Time complexity: O(n^2). The construct method is called n times. Each time you recursively look for the root node, you need to traverse all the elements in the current index range to find the maximum value. In general, the complexity of each traversal is O(logn) and the total complexity is O(nlogn). In the worst case, the array nums is ordered and the total complexity is O(n^2).
Space complexity: O(n). Recursive call depth is n. On average, an array of length N has a recursive call depth of O(logn).
Merge binary trees
Given two binary trees, imagine that when you overlay one of them on top of the other, some nodes of the two binary trees will overlap.
You need to merge them into a new binary tree. The rule for merging is that if two nodes overlap, their values are added as the new value of the nodes merged, otherwise a node that is not NULL is directly added as a node in the new binary tree.
Train of thought
Use preorder traversal to traverse both trees simultaneously.
- Determine the recursive parameters and return values: the pass parameter is the root node of two binary trees, and the return value is the root node of the combined binary tree;
- Recursive termination condition: Return T2 when t1 is null. Conversely, when T2 is empty, return T1.
- Single-level recursive logic: Add the values of two trees when neither node is empty. Then, merge the left and right subtrees of both trees.
The code is as follows:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
TreeNode node = new TreeNode(root1.val + root2.val);
node.left = mergeTrees(root1.left, root2.left);
node.right = mergeTrees(root1.right, root2.right);
returnnode; }}Copy the codeThe last
Ok, so this is the end of the modification and construction of the binary tree, just to review, we just need to switch the left and right children of each node to complete the flipping of the binary tree. The solution idea of constructing binary tree is to find the middle node, and then find the interval of the left subtree and the interval of the right subtree, so as to construct the binary tree recursively. Merging binary trees We can merge two trees by traversing them simultaneously in a pre-order way. I believe that after reading this article, you will have a certain understanding of binary tree traversal, thank you for reading.
Previous articles:
- StoreKit2 smells this good? Yeah, I tried it. It smells good
- After reading this article, I am no longer afraid of being asked how to construct a binary tree.
- The game guys are trying to get people to pay again. That’s bad!
- Take you rolled a netease holding cloud music home | adapter
- Netease Cloud Music Home Page (3)
- Netease Cloud Music Home Page (2)
- Netease Cloud Music Home Page (a)
- Does the code need comments? Write and you lose
- I would not study in Codable for a long time. They are for fun
- IOS handles web data gracefully. Do you really? Why don’t you read this one
- UICollectionView custom layout! This one is enough
Please drink a cup ☕️ + attention oh ~
- After reading, remember to give me a thumbs-up oh, there is 👍 power
- Follow the public number – HelloWorld Jie Shao, the first time push new posture
Finally, creation is not easy, if it is helpful to you, I hope you can praise and support, what questions can also be discussed in the comments section 😄 ~