Contact us: Youdao Technical team assistant: ydtech01 / email: [email protected]
preface
This article is part two of a series on hand tearing algorithms called Do you Really Know binary trees?
If you haven’t already seen Part 1, Do you Really Know binary Trees, it’s highly recommended that you read part 1 so that you’ll be better equipped to solve the problem. Much of what was covered in the first chapter will not be repeated here.
Binary tree base brush part
1.1 LeetCode 144 Preorder traversal of binary trees
Their thinking
If you read my last article, “Do you Really know binary trees?”, you already know that our tree traversal is inherently recursive.
In addition, also talked about how to design and implement a recursive function, if the two points do not understand or did not read the last article students, please first move to “do you really understand binary trees (tree structure foundation)” to make up the foundation first, here is not repeated, directly talk about ideas:
First, let’s design our recursive function
- Traversal the binary tree with root as the root node
- Boundary condition: if root is empty, root is directly returned without traversal
- Recursive process: pre-traversal the left subtree and pre-traversal the right subtree respectively
Code demo
/* * @lc app=leetcode.cn id=144 lang=typescript * * [144] binary tree traversal */
// @lc code=start
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */
function preorderTraversal(root: TreeNode | null, arr: number[]=[]) :number[] {
// Determine the boundary condition
if(root) {
// Add the root node to the array first because it is pre-traversal
arr.push(root.val);
// Recursively traverse the left and right subtrees
preorderTraversal(root.left, arr);
preorderTraversal(root.right, arr);
}
return arr;
};
// @lc code=end
Copy the codeThe above is the conventional recursive way to achieve, we can also use the iterative way to achieve:
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
* @return {number[]}* /
var preorderTraversal = function(root) {
// Complete the iteration with a stack assist
const stack = [];
// Result array
const res = [];
// The current node
let cur = root;
// End the loop if the current node is empty or the stack is empty
while(cur || stack.length>0) {
while(cur) {
// The root node is stored in the result array first
res.push(cur.val);
// In order to go back to the root node and continue traversing the right subtree when we get to the bottom of the left subtree, we stack the root node first
stack.push(cur);
// Continue traversing the left subtree until you reach the leaf node
cur = cur.left;
}
// Now that we have traversed the left subtree, we need to traverse the right subtree by popping the nearest root node from the top of the stack
cur = stack.pop();
// Iterate over the right subtree of the popup root node
cur = cur.right;
}
return res;
};
Copy the code1.2 LeetCode 589 N tree traversal
Their thinking
So we’re going to do the exact same thing that we did with binary trees, so I’m not going to go over it here.
First, let’s design our recursive function
- Function Meaning: Traverses the n-fork tree with root as the root node
- Boundary condition: if root is empty, no traversal is required and the result array is returned directly
- Recursive process: All subtrees under root are recursively traversed
Code demo
/* * @lc app=leetcode.cn id=589 lang=typescript * * [589] N fork-tree traversal */
// @lc code=start
/** * Definition for node. * class Node { * val: number * children: Node[] * constructor(val? : number) { * this.val = (val===undefined ? 0 : val) * this.children = [] * } * } */
function preorder(root: Node | null, arr: number[] = []) :number[] {
// Boundary conditions
if(! root)return arr;
// Place the root node in the result array
arr.push(root.val);
// Loop recursively calls all child nodes
root.children.forEach(child= > {
preorder(child, arr);
});
return arr;
};
// @lc code=end
Copy the code1.3 LeetCode 226 Inverts the binary tree
Their thinking
To reverse a binary tree, we first reverse the left and right subtrees of the binary tree, and then reverse the left and right subtrees of the root node.
Here we use the new features of DECONSTRUCtion assignment in JS for efficient and rapid inversion.
First, let’s design our recursive function
- Reverse the binary tree with root as the root node
- Boundary condition: if root is empty, return root directly without inversion
- Recursion: Reverse the left and right subtrees of root, respectively
Code demo
/* * @lc app=leetcode.cn id=226 lang=typescript * * [226] Flip binary tree */
// @lc code=start
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */
function invertTree(root: TreeNode | null) :TreeNode | null {
// boundary condition, return when root is empty
if(! root)return root;
// Swap the left and right subtrees of root
[root.left, root.right] = [root.right, root.left];
// Recurse left and right subtrees respectively
invertTree(root.left)
invertTree(root.right)
return root;
};
// @lc code=end
Copy the code1.4 LeetCode means Offer32. Print binary tree ⅱ from top to bottom
Their thinking
This problem is actually our binary tree sequence traversal, each layer of nodes output in turn. A trick here is to add a variable k that represents the level of the binary tree currently traversed. The default is 0, which means the default is the first level of the binary tree.
First, let’s design our recursive function
- Add the left and right subtrees of the root node to the array where the current layer k resides
- Boundary condition: if root is empty, no traversal is required and the result array is returned directly
- Recursion: Recursively traverse the left and right subtrees of root, adding 1 to the number of levels
Code demo
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */
function levelOrder(root: TreeNode | null,k=0, res: number[][] = []) :number[] []{
// Boundary condition, if root does not exist, returns the result array directly
if(! root)return res;
// If the length of the result array is k, we are going to iterate through a new layer, but there is no array for this layer to hold data, so we need to create a new array and place it at the end of the result array
if(res.length===k) res.push([]);
// Put the value of the root node into the KTH bit of the array
res[k].push(root.val);
// Recursively traverses the left and right subtrees
levelOrder(root.left, k+1, res);
levelOrder(root.right, k+1, res);
return res;
};
Copy the codeOur binary tree traversal can be achieved not only by recursion, but also by queue + iteration, with similar ideas
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */
function levelOrder(root: TreeNode | null, res: number[][]=[]) :number[] []{
// Boundary condition, root does not exist to return an empty array
if(! root)return res;
// Use a queue to store nodes. The root node is initially queued
const queue: TreeNode[] = [root];
// It is used to record the current traversal level
let k = 0;
while(queue.length! = =0) {
// When the number of layers is the same as the length of the result array, it indicates that the next layer is traversed, but there is no array to store the data of the next layer, so an empty array is placed at the end of the result array
if(k===res.length) res.push([]);
// All nodes in the queue are the nodes of the current layer and are arranged from left to right
let queueLen = queue.length;
// Note that the terminating condition of this line is for the length of the loop. If an element is added to the queue dynamically during the loop, it will not be added to the loop. Therefore, it can be added during the loop
// Continuously push the child nodes of the element with child nodes into the queue without worrying about the next layer of data being printed on the same line
while(queueLen--) {
// When the root node exits the queue and presses the result into the array at layer K
const item = queue.shift();
res[k].push(item.val);
// If the left subtree exists, the left subtree joins the queue
item.left && queue.push(item.left);
// If the right subtree exists, the right subtree is in the queue
item.right && queue.push(item.right);
}
// After all nodes of this layer are processed, remember to increase the number of layers by one, ready to traverse the next layer
k++;
}
return res;
};
Copy the code1.5 LeetCode 107 Sequence traversal of binary tree ⅱ
Their thinking
This problem is no different from the previous problem, just the result array of the previous problem reversed, this in JS implementation is extremely simple, no further details.
Code demo
/* * @lc app=leetcode.cn id=107 lang=typescript * * [107] Binary tree traversal II */
// @lc code=start
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */
function _lavelOrder(root: TreeNode|null, k: number, arr: number[][] = []) :number[] []{
if(! root)return arr;
if(arr.length===k) arr.push([]);
arr[k].push(root.val);
_lavelOrder(root.left, k+1, arr);
_lavelOrder(root.right, k+1, arr);
return arr;
}
function levelOrderBottom(root: TreeNode | null) :number[] []{
const res = _lavelOrder(root, 0);
// Use a double pointer to swap an inverted array
for(let i=0,j=res.length-1; i<j; i++,j--) { [res[i], res[j]] = [res[j], res[i]]; }return res;
// You can also use the built-in inversion method of arrays
// return res.reverse();
};
// @lc code=end
Copy the code1.6 Serrated sequence traversal of LeetCode 103 binary tree
Their thinking
This problem is actually a synthesis of the ideas of the above two problems. We just need to iterate the output to get the result array according to the normal layer order, and then reverse the odd lines in the result array.
Of course, we can do a better way, which is to do a hierarchy walk, and determine whether the current number of layers k is odd or even. If it is odd, we add elements to the front of the array, otherwise we add elements to the back of the array, so we don’t need to invert the array.
Code demo
Scheme 1: Normal sequence traversal first, and then invert the array of odd rows
function _zigzagLevelOrder(root: TreeNode | null, k:number=0, res: number[][]=[]) :number[] []{
if(! root)return res;
if(k===res.length) res.push([]);
res[k].push(root.val);
_zigzagLevelOrder(root.left, k + 1, res);
_zigzagLevelOrder(root.right, k + 1, res);
return res;
};
function zigzagLevelOrder(root: TreeNode | null) :number[] []{
const res = _zigzagLevelOrder(root);
// Invert the odd rows
return res.map((item, index) = > {
if(index&1) {
item = item.reverse();
}
returnitem; })}Copy the codeScheme 2: In sequential traversal, if k is odd, add elements from the front of the array; otherwise, add elements from the back
function _zigzagLevelOrder(root: TreeNode | null, k:number=0, res: number[][]=[]) :number[] []{
if(! root)return res;
if(k===res.length) res.push([]);
(k&1)? res[k].unshift(root.val):res[k].push(root.val); _zigzagLevelOrder(root.left, k +1, res);
_zigzagLevelOrder(root.right, k + 1, res);
return res;
};
function zigzagLevelOrder(root: TreeNode | null) :number[] []{
return _zigzagLevelOrder(root);
}
Copy the codeTwo, binary tree advanced brush part
2.1 LeetCode 110 Balanced binary tree
Their thinking
Concept: A tree whose absolute value of the height difference between the left and right subtrees is no more than 1 is called a balanced binary tree.
Then, according to the question, we can think of is the calculation of a tree left and right subtrees of tree height, and then see if their poor absolute value is greater than 1, in order to use a recursive alone determine whether the tree is balanced tree, we can at the time of calculation of tree height, assume that if the tree is not balanced tree, that is the absolute value of left and right subtrees tree height difference is greater than 1, We just return a negative number, such as -1, so that when our program is done, we can tell if the current tree is a balanced tree by checking whether the tree height is less than 0.
First, let’s design our recursive function
- Return a negative number if the tree is unbalanced while calculating the height of the tree where root is the root node
- Boundary condition: When root is empty, the tree height is 0
- Recursive process: calculate the height of the left and right subtrees respectively. The height of the whole tree is the maximum height of the left and right subtrees plus one
Code demo
/* * @lc app=leetcode.cn id=110 lang=typescript * * [110] Balanced binary tree */
// @lc code=start
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */
function getHeight(root: TreeNode | null) :number {
// If the root node is empty, then the tree height is 0
if(! root)return 0;
// Calculate the height of the left and right subtrees respectively
const lH = getHeight(root.left);
const rH = getHeight(root.right);
// Assume: if the left and right subtrees of the current root are not balanced, return a negative number, such as -1
// If the height of the left and right subtrees is less than 0, their subtrees are already unbalanced
if(Math.abs(lH-rH)>1 || lH < 0 || rH < 0) return -1;
// The height of a tree should be the maximum height of the left and right subtrees plus one
return Math.max(lH, rH) + 1;
}
function isBalanced(root: TreeNode | null) :boolean {
// The tree is balanced as long as its height is greater than or equal to zero
return getHeight(root) >= 0;
};
// @lc code=end
Copy the code2.2 LeetCode 112 Total of paths
Their thinking
In this way, when we find the leaf node, as long as the value of the leaf node is equal to the value of targetNum, if the value of the leaf node is equal to targetNum, That means there’s a path.
First, let’s design our recursive function
- Function meaning: Whether a binary tree with root nodes can find a value where the sum of nodes is equal to targetNum
- Boundary conditions: When root is empty, it cannot exist, return false. In addition, if the current node is a leaf node (a node with no left and right subtrees), the value of this node must be equal to targetNum
- Recursive process: Recursively determine whether the left and right subtrees meet the conditions. It should be noted that the targetNum passed into the recursive function needs to be interpolated with the current node and then passed.
Code demo
/* * @lc app=leetcode.cn id=112 lang=typescript * * [112] Total paths */
// @lc code=start
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */
function hasPathSum(root: TreeNode | null, targetSum: number) :boolean {
// Boundary condition, if root is empty, return false
if(! root)return false;
// If the current node is a leaf node, the value of this node must be targetSum
if(! root.left && ! root.right)return root.val === targetSum;
// Search the left subtree to see if there is a path that satisfies the condition
if(root.left && hasPathSum(root.left, targetSum - root.val)) return true;
// Search the right subtree to see if there is a path that satisfies the condition
if(root.right && hasPathSum(root.right, targetSum - root.val)) return true;
// Return false if none of these conditions are met
return false;
};
// @lc code=end
Copy the code2.3 LeetCode 105 constructs a binary tree by traversing sequences of preorder and middle order
Their thinking
Those of you who have read my previous article “Do you really know binary trees?” will be familiar. In the last article, we have analyzed the solution of this problem on the level of thinking logic, but there is no coding together, now to repay the debt.
Here’s the general idea:
- The first step is to locate the root node
- Recursively build the left subtree
- Recursively build the right subtree
- Then hang the left and right subtrees on the root node
# preorder traversal output < 1 > 2, 3, 4, 5 # sequence traversal of the output < 1 > 2 4 # 3 we know preorder traversal of the first is our root node of the binary tree, then, we according to the root node values in the sequence traversal find location # 1 in this way, we know, 5 is left subtree, 3, 2 and 4 are the sequence of the right subtree of 1. The left subtree does not need further processing, while the right subtree can be directly recursively processed to get the final resultCopy the codeCode demo
/* * @lc app=leetcode.cn id=105 lang=typescript * * [105] Construct a binary tree by traversing pre-order and middle-order sequences */
// @lc code=start
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */
function buildTree(preorder: number[], inorder: number[]) :TreeNode | null {
if(preorder.length===0) return null;
// Used to record the position of the root node in the middle-order traversal
let pos = 0;
// Find the position of the root node in the middle traversal sequence
while(inorder[pos] ! == preorder[0]) ++pos;
// Store the pre-order and middle-order traversal sequences of the split left and right subtrees
let l_pre = [], l_in = [], r_pre=[],r_in=[];
// Store the pre-traversal and middle-traversal sequences of the left subtree
for(let i=0; i<pos; i++) { l_pre.push(preorder[i+1]);
l_in.push(inorder[i]);
}
// Store the sequence of the right subtree's pre-traversal and middle-traversal
for(let i=pos+1; i<preorder.length; i++) { r_pre.push(preorder[i]); r_in.push(inorder[i]); }// Build a binary tree
const node = new TreeNode(preorder[0], buildTree(l_pre, l_in), buildTree(r_pre, r_in));
return node;
};
// @lc code=end
Copy the code2.4 Number of nodes in LeetCode 222 complete binary tree
Their thinking
This problem is to calculate how many nodes there are in a tree. We only need to know the formula: number of summary points = number of left subtree nodes + number of right subtree nodes + number of root nodes (1)
Code demo
/* * @lc app=leetcode.cn id=222 lang=typescript * * [222] Number of nodes in a complete binary tree */
// @lc code=start
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */
function countNodes(root: TreeNode | null) :number {
// Boundary condition, return 0 if root does not exist
if(! root)return 0;
return countNodes(root.left) + countNodes(root.right) + 1;
};
// @lc code=end
Copy the code2.5 LeetCode refers to the KTH largest node in Offer 54 binary search tree
Their thinking
Binary search tree: All values in the right subtree are greater than the root node, and all nodes in the left subtree are less than the root node. Therefore, the middle-order traversal output of a binary search tree must be an ordered array.
Since this is a binary search tree, the left subtree must be smaller than the root node, and the right subtree must be larger than the root node. From this feature we can conclude:
- If we want to find the KTH largest tree, and k is less than or equal to the number of nodes in the right subtree, we can just go to the right subtree,
- If k is equal to the number of nodes in the right subtree plus 1, then what we’re looking for is actually the root node
- If that’s not the case, then we just look in the left subtree, but now that we’ve eliminated the root and the right subtree, instead of looking for the KTH largest node in the left subtree, we should subtract the root and the right subtree
Code demo
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */
// Number of compute nodes
function getCount(root: TreeNode) :number {
if(! root)return 0;
return getCount(root.left) + getCount(root.right) + 1;
}
// Since this is a binary search tree, the left subtree must be smaller than the root, and the right subtree must be larger than the root
// From this feature we can conclude:
If k is less than or equal to the number of nodes in the right subtree, then we can look in the right subtree first.
// If k is equal to the number of nodes in the right subtree plus 1, then we are looking for the root node
// If it is not, then we look directly in the left subtree, but since we have excluded the root and the right subtree, instead of looking for the KTH largest node in the left subtree, we should subtract the root and the right subtree
function kthLargest(root: TreeNode | null, k: number) :number {
// Get the number of right subtree nodes
const count_r = getCount(root.right);
// If k is less than or equal to the number of nodes in the right subtree, find the KTH largest tree in the right subtree
if(k<=count_r) return kthLargest(root.right, k);
// If k is equal to the number of nodes in the right subtree plus 1, the tree is the root
if(k===count_r+1) return root.val;
K -(count_r+1)=k- count_r-1 (count_r+1)=k- count_r-1
return kthLargest(root.left, k - count_r - 1);
};
Copy the code2.6 LeetCode refers to the substructure of the Offer 26 tree
Their thinking
So what we’re going to do in this problem is we’re going to see if B matches the whole tree of A, and if it doesn’t, we’re going to see if B matches the left subtree of A or the right subtree of A, and if it matches any of them, then B is A substructure of A.
Code demo
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */
// Recursively matches the subtree structure
function isMatch(a: TreeNode, b: TreeNode) {
// If b is empty, it must match and returns true
if(! b)return true;
// No match is possible if a is empty, return false
if(! a)return false;
If the values of a and B are inconsistent, return false
if(a.val ! == b.val)return false;
// Recursively match the left and right subtrees of A and B, respectively
return isMatch(a.left, b.left) && isMatch(a.right, b.right);
}
function isSubStructure(A: TreeNode | null, B: TreeNode | null) :boolean {
If B is empty, it is not a substructure of any tree
if(! B)return false;
// if A is null and B is not null, no match is possible and false is returned
if(! A)return false;
// Recursively determine whether A and B can match, and if so, return true
if(isMatch(A, B)) return true;
// If the left and right subtrees of A match each other, the match is successful. If the left and right subtrees match each other, the match is successful
return isSubStructure(A.left, B) || isSubStructure(A.right, B);
};
Copy the code2.7 Maximum width of LeetCode 622 binary tree
Their thinking
This problem is indeed difficult to implement, we can use the last article “do you really know binary trees (tree structure basics)” described in the complete binary tree numbering method and a queue to help us complete this problem. In the complete binary tree number, if the current node number is I, then the number of its left subtree is 2 * I, and the number of its right subtree is 2 * I +1. However, in this problem, it is possible that the number is too large to cause the plastic data overflow, so we need special treatment. Specific solution ideas, code notes are written very clearly, directly look at the code.
Code demo
/* * @lc app=leetcode.cn id=662 lang=typescript * * [662] Maximum width of binary tree */
// @lc code=start
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */
// To facilitate the storage node and its corresponding number, define a wrapper class
class Wrapper {
constructor(public node: TreeNode, public idx: number){}}function widthOfBinaryTree(root: TreeNode | null) :number {
// Store the result
let res = 0;
// Define a queue of wrapper classes that can store nodes and their corresponding numbers
const queue: Wrapper[] = [];
// Queue the root node and its number 0
queue.push(new Wrapper(root, 0));
// Used to store the number of nodes in each layer
let rowSize;
while(rowSize = queue.length) {
// Set the minimum and maximum number of the current layer to the parent node
let lIdx = queue[0].idx, rIdx = queue[0].idx;
// Iterate over each element of the current layer
while(rowSize--) {
// Get the team leader out of the team
const { node, idx } = queue.shift();
// The maximum number of the current layer is the number of the parent node
rIdx = idx;
// If there is a left subtree, create a wrapper class using the left subtree and its corresponding number, and add it to the queue
// The most difficult part is how to define the number.
// We have learned the complete binary tree numbering method, can refer to this numbering method,
// The root node of the ith node is numbered 2* I, and the right subtree is numbered 2* I +1
Idx * 2 and idx * 2 + 1 represent left and right subtrees
// If we commit this way, we run into a problem that when our tree is large enough, this number will exceed
// Our integer range, so how can we reduce this number without affecting the results of the program, avoid integer overflow
// The minimum and maximum numbers are 6 and 7, respectively, which are essentially the same as 0 and 1
// The difference between 7 and 6 is the same as the difference between 1 and 0
// We can reduce the size of the parent node by making the current number lIdx
node.left && queue.push(new Wrapper(node.left, (idx - lIdx) * 2));
node.right && queue.push(new Wrapper(node.right, (idx - lIdx) * 2 + 1));
}
// At the end of the loop, we just need to calculate the width of the previous layer, and the maximum number of the current layer minus the minimum number plus 1, then take the maximum of both to find the maximum width
// For example, the minimum and maximum numbers of the current layer are 0 and 8, then this layer actually has 8-0+1=9 node space, i.e. width is 9.
res = Math.max(res, rIdx - lIdx + 1);
}
return res;
};
// @lc code=end
Copy the code