Do you really know binary trees?

Series article guide

• Kiner algorithm brush topic (a) : linked list and linked list ideas
• Kiner algorithm: Recursion and stack (solve the expression evaluation problem)
• Kiner algorithm brush topic (3) : thread pool and task queue
• Do you really know binary trees?
• Do you really know binary trees?
• Kiner algorithm: Heap and Priority queue
• Kiner algorithm brush topic (five) : Heap (priority queue)

The open source project

All articles in this series will be collected and managed in GitHub. Welcome ISSUE and Star.

GitHub portal: Kiner algorithm

preface

This article is part two of a series on hand tearing algorithms called Do you Really Know binary trees? If you haven’t seen Part 1 do you really know binary trees, it’s highly recommended that you read part 1 so that you’ll be better at solving problems. Much of what was covered in the first chapter will not be repeated here.

Binary tree base brush part

LeetCode 144 Preorder traversal of binary trees

Their thinking

If you have read my previous article you really understand what is binary tree (tree), you should already know, suit to use our tree traversal is inherently recursive implementation, in addition, also about how to design and implement a recursive function, if the two don’t know or haven’t seen an article on the classmate, Do you really know binary trees? (Tree structure basics)

First, let’s design our recursive function

1. Traversal the binary tree with root as the root node
2. Boundary condition: if root is empty, root is directly returned without traversal
3. 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 code

The 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 code

LeetCode 589 antecedent traversal of n-fork tree

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

1. Function Meaning: Traverses the n-fork tree with root as the root node
2. Boundary condition: if root is empty, no traversal is required and the result array is returned directly
3. 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 code

LeetCode 226 flips binary trees

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

1. Reverse the binary tree with root as the root node
2. Boundary condition: if root is empty, return root directly without inversion
3. 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 code

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

1. Add the left and right subtrees of the root node to the array where the current layer k resides
2. Boundary condition: if root is empty, no traversal is required and the result array is returned directly
3. 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 code

Our 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 code

Sequence Traversal of LeetCode 107 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 code

Zigzag sequence traversal for 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

/* * @lc app=leetcode.cn id=103 lang=typescript * * [103] Binary tree zigzag 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) * } * } */

// Do a normal sequence traversal, 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);
// // inverts the odd rows
// return res.map((item, index) => {
// if(index&1) {
// item = item.reverse();
/ /}
// return item;
/ /})
// }

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);
}
// @lc code=end


Copy the code

Binary tree advanced brush problem part

LeetCode 110 balanced binary trees

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

1. Return a negative number if the tree is unbalanced while calculating the height of the tree where root is the root node
2. Boundary condition: When root is empty, the tree height is 0
3. 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 code

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, it indicates that the path exists.

First, let’s design our recursive function

1. Function meaning: Whether a binary tree with root nodes can find a value where the sum of nodes is equal to targetNum
2. 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
3. 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 code

LeetCode 105 constructs a binary tree by traversing sequences of preorder and middle order

Their thinking

If you have read my last article do you really understand binary trees (tree structure foundation) students should not be unfamiliar, in the last article, has taken everyone in the level of thinking logic analysis of the solution to the problem, but did not code together, now to pay off the debt.

Here’s the general idea:

1. The first step is to locate the root node
2. Recursively build the left subtree
3. Recursively build the right subtree
4. Then hang the left and right subtrees on the root node

Preorder traversal the output<1> 5, 2, 3, 4The output is traversed in order5 <1> 3, 2, 4# We know that the first digit of the preorder traversal is the root node of our binary tree, so we find the position of 1 in the middle order traversal according to the value of the root node
# In this way, we know that 5 is the left subtree, 3, 2 and 4 are the sequence of the right subtree of 1. The left subtree does not need to continue processing, and the right subtree can be directly recursively processed to get the final result
Copy the code

Code 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 code

LeetCode 222 Number of nodes in a 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 implementation

/* * @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 code

LeetCode refers to the KTH largest node in the 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 tree of the left subtree must be smaller than the root node, and the tree of the right subtree must be larger than the root node.

1. 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,
2. 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
3. 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 code

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 code

LeetCode 622 Maximum width of binary tree

Their thinking

Do you really know binary trees? (Tree structure basics) 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