Preface:

Weekend boring, sort out the binary tree related topics of LeetCode done before, also convenient for future continuous review, LeetCode topic is always brushed after the feeling will, after a period of time and forget, or to keep repeating.

The full text is about 3.5W words, a total of 47 topics, it is recommended to collect slowly to see, there are wrong places welcome to correct!

The nugget has a word limit, so it’s divided into two pieces,This is the first article, welcome to follow the update!

For trees, the most common one is a binary tree. In addition to the basic operation of binary tree, we also need to understand some special binary tree, such as binary search tree, balanced binary tree, and so on. In addition, we need to be familiar with the way of binary tree traversal, such as fore-ordered traversal, middle-ordered traversal, post ordered traversal, and hierarchical traversal. In addition, we also need to know the common way of binary tree traversal: depth first traversal and breadth first traversal.

1. The concept of binary trees

There are three similar concepts of “trees” : Height, Depth, and Level. Their definition goes like this:

• Height of node: Longest path from node to leaf node (number of edges)
• Node depth: The number of edges traversed from the root node to this node
• Node layer: Node depth +1
• Tree height: The height of the root node

(1) Binary tree

Binary tree is a special kind of tree. It refers to the ordered tree in which the degree of nodes in the tree is not greater than 2. It is the simplest and most important tree. The recursion of binary tree is defined as: binary tree is an empty tree, or a non-empty tree composed of a root node and two non-intersecting left and right subtrees called roots respectively; The left subtree and the right subtree are both binary trees.

Binary trees have the following characteristics:

• Each node has at most two subtrees, and the degree of a node is at most two (the number of subtrees a node contains is called the degree of the node).
• The left subtree and the right subtree are ordered, and the order cannot be reversed.
• Even if a node has only one subtree, you have to distinguish between left and right subtrees.

There are two ways to store binary trees,

• Binary chain storage based on Pointers or references,
• Sequential storage based on arrays.

1) Chain storage method. As you can see in the figure below, each node has three fields, one of which stores data and the other two are Pointers to the left and right child nodes. By holding the root node, we can string the tree through the left and right child nodes. This type of storage is quite common. Most binary tree code is implemented through this structure.

2) Sequential storage method. If the root node is stored at the position of subscript I = 1, the left child node is stored at the position of subscript 2 * I = 2, and the right child node is stored at the position of subscript 2 * I + 1 = 3. In the same way, the left child node of node B is stored at 2 * I = 2 * 2 = 4, and the right child node is stored at 2 * I + 1 = 2 * 2 + 1 = 5.

If node X is stored in an array at the subscript I, the left child node is stored at the subscript 2 * I, and the right child node is stored at the subscript 2 * I + 1. Conversely, the location store subscript I /2 is its parent node. In this way, as long as you know where the root node is stored (normally, the root node will be stored at the subscript 1 to facilitate the calculation of child nodes), you can string the whole tree through the subscript calculation.

However, the above is a complete binary tree, so only one storage location with subscript 0 is “wasted”. If it’s not a complete binary tree, it actually wastes a lot of array storage. Look at this example:

So, if a binary tree is a full binary tree, then array storage is definitely the most memory efficient way. Because array storage does not need to store additional left and right child Pointers, as in chained storage. That’s why a complete binary tree is singled out, and that’s why it requires all the children at the last level to be left.

(2) Full binary tree

All branches have left and right subtrees, and all the leaves are on the same level, so it’s a full binary tree. It means perfect and perfect, and the key is the balance of the tree.

According to the definition of full binary tree, its characteristics are:

1. Leaves can only appear at the bottom layer.
2. The degree of non-leaf must be 2.
3. In the same depth of the binary tree, the full binary tree has the most nodes, the leaf tree has the most.

(3) Complete binary tree

If a binary tree with n nodes is numbered in order, it is a complete binary tree if the node numbered I is in exactly the same position as a full binary tree with the same depth and the node numbered I is in exactly the same position. A full binary tree must be a complete binary tree, and the reverse is not necessarily true. The key is to number them in sequence and then look for them accordingly. Here is a complete binary tree:

Combined with the definition of complete binary tree, its characteristics are obtained:

1. Leaves can only appear at the bottom level (inherited from the full binary tree)
2. The lowest leaf nodes must be clustered in the left continuous position.
3. The penultimate layer, if there are leaf nodes, must appear in the right continuous position.
4. Similarly, the binary tree of node tree, complete binary tree has the least depth (full binary tree is also correct).

Properties of a complete binary tree:

1. A complete binary tree with n nodes has a depth of K = “log2n” +1(down integers).
2. If all nodes of a complete binomial tree with n nodes are stored sequentially, there are the following relationships among nodes: if I is node number (numbering from 1), if I >1, the number of its parent is I /2;
3. If 2 * I <= n, then the number of the left son (the root of the left subtree) is 2 * I; If 2 * I > n, there is no left son; If 2 * I + 1 <= n, then the node of its right son is numbered 2 * I + 1; If 2 * I + 1 > n, there is no right son.

(4) Binary search tree

Binary search tree is the most common type of binary tree, also called binary search tree. As the name suggests, binary search trees are designed to achieve fast search. However, it supports not only quick lookup of a piece of data, but also quick insertion and deletion of data.

The value of the root node of the binary search tree is greater than the value of any node in its left subtree and less than the value of any node in its right node.This rule applies to every node in a binary search tree. Here is a binary search tree:

A binary sort tree is either an empty binary tree or has the following characteristics:

• If the root has a left subtree, then everything in the left subtree is less than the root;
• If the root has a right subtree, then the values of all the nodes in the right subtree are the same as the values of the root;
• The left and right subtrees are also required to be binary sorting trees;
• In binary search tree, we try to avoid the case that two nodes are equal in value.
• In order to binary search tree traversal, you can output a small to large ordered data queue.

When the binary search tree is used to perform the search operation, the following judgments can be made:

• We first determine if the root is equal to the data we are looking for, and if so, we return it.
• If the root is larger than the data to look for, the lookup is performed recursively in the left subtree until it reaches the leaf node.
• If the root is smaller than the data to look for, the lookup is performed recursively in the right subtree until it reaches the leaf node.
• The time complexity of binary search can be reduced to order logn.

(5) Balanced Binary Search Tree (AVL)

Balanced binary search trees have the following properties:

1. It could be an empty tree.
2. If it is not an empty tree, the left and right subtrees of any node are balanced binary trees, and the absolute value of the height difference does not exceed 1.

Here is a balanced binary tree.

Balanced binary tree is to solve the binary search tree chain structure (only left subtree or only right subtree), such a situation does not help our search, but increases the cost of maintenance.

The balance factor is denoted by two letters. The first letter represents the balance factor of the root node of the least unbalanced subtree, and the second letter represents the balance factor of the root node of the higher subtree of the least unbalanced subtree. Different methods are used to adjust the unbalanced subtree according to different situations.

2. Binary tree operations

As for the binary tree data structure, data can be added, deleted and searched through the tree only when the traversal problem is solved. The so-called binary tree traversal refers to: starting from the root node of the tree, in some order to access all nodes in the binary tree, so that each node is accessed only once.

Common way of binary tree traversal sequence traversal in preorder traversal, and the sequence traversal sequence traversal, and each can use recursive traversal method and iterative way to achieve, in this case, the sequence is the parent node traversal sequence of traversal sequence is before the parent node, the sequence is middle traverse the parent node, after the order is finally through the parent node. Among themPreorder, in-order, and post-order traversal are based on depth-first traversal, while hierarchical traversal is based on breadth-first traversal.

The structure and coding of binary tree in the figure above:

``````const root = {
val: "A".left: {
val: "B".left: {
val: "D"
},
right: {
val: "E"}},right: {
val: "C".left: {
val: "F"
},
right: {
val: "G"}}};Copy the code``````

(1) Preorder traversal

Basic idea: first access the root node, then the first order traversal of the left subtree, and then the first order traversal of the right subtree, that is, the root – left – right. Traverse result: A -> B -> D -> E -> C -> F -> G

1) Recursive implementation:

``````function preorder(root){
if(! root){return
}

console.log(root.val)  // Prints the node currently traversed
preorder(root.left)    // Recursively traverse the left subtree
preorder(root.right)   // Recursively traverse the right subtree
}
Copy the code``````

2) Non-recursive implementation: initialize a stack and result array, put the root node on the stack, and repeat the following steps when the stack is not empty: (2) If the right child node of top is not empty, put the right child node of top into the stack. (3) If the left child node of top is not empty, put the left child node of top into the stack. (4) Put the removed top element into the result array

``````function preorder(root){
if(! root){return [];
}
var result = []
var stack = [root]
while(stack.length){
var top = stack.pop();
if(top.right){
stack.push(top.right);
}
if(top.left){
stack.push(top.left);
}
result.push(top.val);
}
return result;
}
Copy the code``````

(2) in order traversal

Basic idea: first order traversal left subtree, then access the root node, and finally order traversal right subtree, that is, left – root – right. D -> B -> E -> A -> F -> C -> G

1) Recursive implementation:

``````function inorder(root) {
if(! root) {return
}

inorder(root.left)       // Recursively traverse the left subtree
console.log(root.val)    // Print the node currently traversed
inorder(root.right)      // Recursively traverse the right subtree
}

Copy the code``````

2) Non-recursive implementation: initialize a stack and result array. Repeat the following steps when the stack is not empty: (1) Put the root node and all left child nodes into the stack until there is no left child node. (2) The top element of the stack is out of the stack, stored in the result array, and the element out of the stack is regarded as the root node. (3) Check whether the right child node of the root node has a left child node, if so, push it, otherwise continue to out of the stack

``````function inorder(root) {
if(! root){return [];
}
var result = []
var stack = []
while(stack.length || root){
while(root){
stack.push(root);
root = root.left;
}
root = stack.pop();
result.push(root.val)
root = root.right;
}
return result;
}
Copy the code``````

(3) Sequential traversal

Basic idea: sequential traversal of the left subtree, and then sequential traversal of the right subtree, and finally access the root node, that is, left-right-root. D -> E -> B -> F -> G -> C -> A

1) Recursive implementation:

``````function postorder(root) {
if(! root) {return
}

inorder(root.left)       // Recursively traverse the left subtree
inorder(root.right)      // Recursively traverse the right subtree
console.log(root.val)    // Print the node currently traversed
}
Copy the code``````

2) Non-recursive implementation: initialize a stack and result array, put the root node on the stack, and repeat the following steps when the stack is not empty: (3) If the left child node of top is not empty, put the left child node of top into the stack. (4) If the right child node of top is not empty, put the right child node of top into the stack. (4) If the right child node of top is not empty, put the right child node of top into the stack

``````function postorder(root) {
if(! root){return [];
}
var result = []
var stack = [root]
while(stack.length){
var top = stack.pop();
result.unshift(top.val);
if(top.left){
stack.push(top.left);
}
if(top.right){ stack.push(top.right); }}return result;
}
Copy the code``````

(4) Sequential traversal

Basic idea: Sequential traversal is to print the nodes of a binary tree from top to bottom and left to right. Traverse result: A -> B -> C -> D -> E -> F -> G

Create an array for the results and a queue for the nodes of the binary tree. If the queue for the binary tree is not empty, repeat the following steps: (1) Take the first node of the queue as the root node and put it in the result array (2) put it in the queue if the left subtree of the root node is not empty (3) put it in the queue if the right subtree of the root node is not empty

Basic implementation:

``````function levelTraversal(root){
if(! root){return [];
}
var queue = [root];
var result = [];

while (tree.length){
var node = queue.shift();
result.push(node.val);
if(node.left){
queue.push(node.left);
}
if(node.right){ queue.push(node.right); }}return result;
}
Copy the code``````

(5) Summary

As you can see, in the binary tree traversal, each node is accessed once, and the time complexity is order n. Then, when the location is found and the data is added and deleted, the connection relationship is established through the pointer. For binary trees without any special properties, the time complexity of actually performing the increment and deletion operations is O(1), aside from the time complexity of traversal. The search operation of tree data is the same as that of linked list. It needs to traverse every data to judge, so the time complexity is O(n).

3. Classic topic: Traversal of binary trees

(1) Preorder traversal of binary tree

Given a binary tree, return a preorder traversal of it. Example:

``````Input:1.null.2.3]
1
\
2
/
3Output:1.2.3]
Copy the code``````

Advanced: Recursion is easy, can you do it iteratively?

Iterative implementation: initialize a stack and result array, putting the root node on the stack, and repeat the following steps when the stack is not empty: (2) If the right child node of top is not empty, put the right child node of top into the stack. (3) If the left child node of top is not empty, put the left child node of top into the stack. (4) Put the removed top element into the result array

``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number[]}* /

// Iteration:
var preorderTraversal = function(root) {
if(! root){return [];
}
var result = []
var stack = [root]
while(stack.length! = =0) {var top = stack.pop();
if(top.right){
stack.push(top.right);
}
if(top.left){
stack.push(top.left);
}
result.push(top.val);
}
return result;
};

/ * /
var preorderTraversal = function(root) {
if(! root){return [];
}
var result = []
var preorderTraversalNode = (node) = > {
if(node) {
result.push(node.val)
preorderTraversalNode(node.left)
preorderTraversalNode(node.right)
}
}
preorderTraversalNode(root)
return result
};
Copy the code``````

Complexity of iteration:

• The time complexity of traversing the whole tree is O(N), where N is the number of nodes in the binary tree.
• The spatial complexity is the maximum amount of space the stack can use, and that space is determined by the height of the tree, so the spatial complexity is O(H), where H is the height of the binary tree.

Complexity of recursion:

• The time complexity is O(N), where N is the number of nodes in the binary tree.
• Space complexity, because the depth of the function call stack is related to the height of the tree, so the space used is O(H). H is the height of the binary tree.

(2) in order traversal of binary tree

Given a binary tree, return the in-order traversal of it. Example:

``````Input:1.null.2.3]
1
\
2
/
3Output:1.3.2]
Copy the code``````

Advanced: Recursion is easy, can you do it iteratively?

Iterative implementation: initialize a stack and result array. Repeat the following steps when the stack is not empty: (1) Put the root node and all left child nodes into the stack until there is no left child node. (2) The top element of the stack is out of the stack, stored in the result array, and the element out of the stack is regarded as the root node. (3) Check whether the right child node of the root node has a left child node, if so, push it, otherwise continue to out of the stack

``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number[]}* /

// Iteration implementation:
var inorderTraversal = function(root) {
if(! root){return [];
}
var result = []
var stack = []
while(stack.length! = =0||root){
while(root){
stack.push(root);
root = root.left;
}
root = stack.pop();
result.push(root.val)
root = root.right;
}
return result;
};

// Recursive implementation
var inorderTraversal = function(root) {
if(! root){return [];
}
var result = []
var inorderTraversalNode = (node) = > {
if(node) {
inorderTraversalNode(node.left)
result.push(node.val)
inorderTraversalNode(node.right)
}
}
inorderTraversalNode(root)
return result
};
Copy the code``````

Complexity of iteration:

• The time complexity of traversing the whole tree is O(N), where N is the number of nodes in the binary tree.
• The spatial complexity is the maximum amount of space the stack can use, and that space is determined by the height of the tree, so the spatial complexity is O(H), where H is the height of the binary tree.

Complexity of recursion:

• The time complexity is O(N), where N is the number of nodes in the binary tree.
• Space complexity, because the depth of the function call stack is related to the height of the tree, so the space used is O(H). H is the height of the binary tree.

(3) Back-order traversal of binary tree

Given a binary tree, return a sequential traversal of it. Example:

``````Input:1.null.2.3]
1
\
2
/
3Output:3.2.1]
Copy the code``````

Advanced: Recursion is easy, can you do it iteratively?

Iterative implementation: binary tree after the order of traversal and preorder traversal is a reverse process, so the basic idea and preorder traversal is similar. Initialize a stack and the resulting array, placing the root node in the stack. Repeat the following steps when the stack is not empty: (3) If the left child node of top is not empty, put the left child node of top into the stack. (4) If the right child node of top is not empty, put the right child node of top into the stack. (4) If the right child node of top is not empty, put the right child node of top into the stack

``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number[]}* /

// Iteration implementation:
var postorderTraversal = function(root) {
if(! root){return [];
}
var result = []
var stack = [root]
while(stack.length! = =0) {var top = stack.pop();
result.unshift(top.val);
if(top.left){
stack.push(top.left);
}
if(top.right){ stack.push(top.right); }}return result;
};

// Recursive implementation
var postorderTraversal = function(root) {
if(! root){return [];
}
var result = []
var postorderTraversalNode = (node) = > {
if(node) {
postorderTraversalNode(node.left)
result.push(node.val)
postorderTraversalNode(node.right)
}
}
postorderTraversalNode(root)
return result
};
Copy the code``````

Complexity of iteration:

• The time complexity of traversing the whole tree is O(N), where N is the number of nodes in the binary tree.
• The spatial complexity is the maximum amount of space the stack can use, and that space is determined by the height of the tree, so the spatial complexity is O(H), where H is the height of the binary tree.

Complexity of recursion:

• The time complexity is O(N), where N is the number of nodes in the binary tree.
• Space complexity, because the depth of the function call stack is related to the height of the tree, so the space used is O(H). H is the height of the binary tree.

(4) Sequence traversal of binary trees

Given a binary tree, you are asked to return the values of the nodes it traverses sequentially. (that is, access all nodes layer by layer, from left to right). Example:

``````Binary tree: [3.9.20.null.null.15.7].3
/ \
9  20
/  \
15   7
Copy the code``````

Returns the result of its hierarchical traversal:

``````[[3],
[9.20],
[15.7]]Copy the code``````

Create an array to store the results and a queue to store the nodes of the binary tree. According to the output requirements, set a level to store the current level. If the binary tree is not empty, repeat the following steps: (1) Take the first node of the queue as the root node and put it into the result array of the current layer (2) if the left subtree of the root node is not empty, put it into the queue (3) If the right subtree of the root node is not empty, put it into the queue (4) After traversing this layer, the next layer is traversed

``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number[][]}* /
var levelOrder = function(root) {
if(! root){return [];
}
var queue = [root];
var result = [];
var level = 0;

while(queue.length! = =0){
result[level]=[];
var levelNum = queue.length;

while(levelNum--){
var node = queue.shift();
result[level].push(node.val);
if(node.left){
queue.push(node.left);
}
if(node.right){
queue.push(node.right);
}
}
level++;
}
return result;
};
Copy the code``````

Complexity analysis:

• Time complexity: each point enters and leaves the queue once, so the asymptotic time complexity is O(n), where n is the number of nodes in the binary tree.
• Space complexity: The number of elements in the queue does not exceed N, so the progressive space complexity is O(n), where n is the number of nodes in the binary tree.

(5) Binary tree hierarchy traversal II

Given a binary tree, return a bottom-up hierarchical traversal of its node values. (that is, according to the layer from the leaf node to the root node layer, layer by layer from left to right traversal). For example, given a binary tree [3,9,20,null,null,15,7],

``````    3
/ \
9  20
/  \
15   7
Copy the code``````

Returns its bottom-up level traversal as:

``````[[15.7],
[9.20],
[3]]Copy the code``````

For this problem, the most straightforward way to sequence a binary tree is to use BFS (breadth first traversal).

Start by creating a queue and putting the current node in it. The node in the queue is always the node of the current layer. It is dequeued, added to the result, and the children of the current node are added to the queue. Repeat the steps until the queue is empty, and you have traversed the entire binary tree.

``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number[][]}* /
var levelOrderBottom = function(root) {
if(! root) {return[]}const queue = []
queue.push(root)
const res = []  // To store the final result

while(queue.length){
const subRes = []  // To store the node values for each layer
const levelSize = queue.length
for(let i = 0; i < levelSize; i++){
const cur = queue.shift()
subRes.push(cur.val)
if(cur.left){
queue.push(cur.left)
}
if(cur.right){
queue.push(cur.right)
}
}
res.unshift(subRes)
}
return res
};
Copy the code``````

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the binary tree. Each node is accessed once. When the result list uses a linked list structure, the time complexity of adding a layer of node values to the head of the result list is O(1), so the total time complexity is O(n).
• Space complexity: O(n), where n is the number of nodes in the binary tree. The space complexity depends on the queue cost, and the number of nodes in the queue cannot exceed N.

(6) Zigzag sequence traversal of binary trees

Given a binary tree, return a zigzag hierarchical traversal of its node values. (that is, first from left to right, then from right to left to the next layer, and so on, alternating between layers). For example: given a binary tree [3,9,20,null,null,15,7]

``````    3
/ \
9  20
/  \
15   7
Copy the code``````

Return zigzag hierarchy traversal as follows:

``````[[3],
[20.9],
[15.7]]Copy the code``````

You can solve this recursively by creating an array at each level, inserting an array from left to right at the odd level and from right to left at the even level.

Here we use I & 1 to determine the parity of the number of layers:

``````i & 1= =1  / / odd
i & 1= =0  / / even
Copy the code``````
``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number[][]}* /
var zigzagLevelOrder = function(root) {
const res = []

function dfs(i, current){
if(! current)return

if(!Array.isArray(res[i])){
res[i] = []
}
if(i & 1){
res[i].unshift(current.val)
}else{
res[i].push(current.val)
}

dfs(i + 1, current.left)
dfs(i + 1, current.right)
}

dfs(0, root)
return res
};
Copy the code``````

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the binary tree. Each node will be traversed only once, with time complexity O(n).
• Space complexity: O(n), where n is the number of nodes in the binary tree. We need to maintain queues of storage nodes and dual-end queues of storage node values with space complexity O(n).

The properties of binary trees

(1) Completeness check of binary trees

Given a binary tree, determine whether it is a _ complete binary tree _. The definition of complete binary tree in Baidu Baike is as follows:

If the depth of the binary tree is h, the number of nodes at all other layers (1 ~ h-1) reaches the maximum except for layer H, and all nodes at layer H are continuously concentrated at the left, which is a complete binary tree. (Note: Layer H may contain 1 or 2 nodes.)

Example 1:

``Input:1.2.3.4.5.6] output:trueExplanation: Every layer up to the last layer is full (i.e., nodes with a value of {1} and {2.3}), and all nodes in the last layer ({4.5.6}) as far to the left as possible.Copy the code``

Example 2:

``Input:1.2.3.4.5.null.7] output:falseExplanation: The value is7The node is not as far to the left as possible.Copy the code``

Tip: There will be between 1 and 100 nodes in the tree.

For this problem, we can use sequence traversal to solve. In the process of sequence traversal, an index is needed to maintain the index of a node. If a node has an index, the index of its left child is index * 2, and the index of its right child is index * 2 + 1.

Here we initialize a queue to store the current node and its index. Use a count to record the number of nodes currently traversed. If index and count + 1 are equal, then the current node is in the correct position and the traversal continues. If not, then the node is missing and the traversal ends. 台湾国

``````/** * 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 {boolean}* /
var isCompleteTree = function(root) {
if(! root){return true
}
let count = 0
const queue = [{ node: root, index: 1 }]

while(queue.length){
const temp = queue.shift()

const node = temp.node
const index = temp.index
// Check whether the current node is the correct sequence value
if(index ! == ++count){return false
}
// Traverse the left and right subtrees of the current node
node.left && queue.push({node: node.left, index: index * 2})
node.right && queue.push({node: node.right, index: index * 2 + 1})}return true
};
Copy the code``````

Complexity analysis:

• Time complexity: O(n), here the worst case is that we need to traverse the whole binary tree, so the time complexity is O(n), where n is the number of nodes in the binary tree;
• Space complexity: O(1), we need to initialize a queue to hold the currently traversed node, this queue is a constant space, so the space complexity is O(1).

(2) The maximum path sum in the binary tree

Given a non-empty binary tree, return its maximum path sum. In this case, a path is defined as a sequence that starts from any node in the tree and goes from parent to child to any node. The path contains at least one node and does not necessarily pass through the root node. Example 1:

``````Input:1.2.3]
1
/ \
2   3Output:6
Copy the code``````

Example 2:

``````Input: [...10.9.20.null.null.15.7]
-10
/ \
9  20
/  \
15   7Output:42
Copy the code``````

For this problem, we can recursively traverse the binary tree, and we want the maximum sum of paths, so the maximum sum of the left and right subtree paths and the value of this node is going to be our solution.

Note:

• A path that extends from the parent node can only enter the left or right subtree, but not both.
• Only when the maximum contribution value is greater than 0, the corresponding child node is selected.
``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number}* /
var maxPathSum = function(root) {
let sum = Number.MIN_SAFE_INTEGER

const dfs = (root) = > {
if(! root){return 0
}
// Calculate the maximum path sum of the left and right subtrees
const left = dfs(root.left)
const right = dfs(root.right)

// Calculate the total maximum path sum
const maxSum = left + root.val + right
sum = Math.max(sum, maxSum)

// Return the currently calculated maximum path
const max = root.val + Math.max(left, right)
return max < 0 ? 0 : max
}
dfs(root)
return sum
};
Copy the code``````

Complexity analysis:

• Time complexity: O(N), where N is the number of nodes in the binary tree. Each node is accessed no more than two times.
• Space complexity: O(N), where N is the number of nodes in the binary tree. The space complexity depends mainly on the number of layers of recursive calls, the maximum number of layers is equal to the height of the binary tree, and the worst case, the height of the binary tree is equal to the number of nodes in the binary tree.

(3) The diameter of the binary tree

Given a binary tree, you need to calculate its diameter. The diameter length of a binary tree is the maximum of the path length of any two nodes. This path may or may not go through the root. Example: Given a binary tree

``````        1
/ \
2   3
/ \
4   5
Copy the code``````

Return 3, whose length is either path [4,2,1,3] or [5,2,1,3].

When we encounter the problem of binary tree, we usually use depth-first and breadth-first traversal. In this case, we need to ask for diameter, so we use depth-first traversal.

Traverse from the root node. When traversing to each node, add the maximum depth of its left and right subtrees together, compare with the result RES, and assign the maximum value to hot search, so that RES will always be the maximum value. Finally, return res. 台湾国

``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number}* /
var diameterOfBinaryTree = function(root) {
let res = 0

function depth(rootNode){
if(! rootNode)return 0

let l = depth(rootNode.left)  // l is the left subtree depth
let r = depth(rootNode.right) // r is the depth of the right subtree

res = Math.max(res, l + r)    // Calculate the maximum diameter l+r and update res so that it is always the maximum
return Math.max(l ,r) + 1     // Return the depth of the subtree rooted by this node
}
depth(root)
return res
};
Copy the code``````

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the binary tree, where the entire binary tree needs to be traversed, so the time complexity is O(n).
• Space complexity: O(h), where H is the maximum depth of the binary tree and is a constant variable.

(4) All paths of the binary tree

Given a binary tree, return all paths from the root node to the leaf node. Note: A leaf node is a node with no child nodes. Example:

``````Input:1
/   \
2     3
\
5Output:"1 - > 2 - > 5"."1 - > 3"The path from all root nodes to leaf nodes is:1->2->5.1->3
Copy the code``````

The problem is to do a depth-first traversal of a binary tree, and store the value of the current node in the string during the traversal. Until there are no children nodes, the resulting string is stored in the result array.

``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {string[]}* /
var binaryTreePaths = function(root) {
if(! root)return []

let res = []
const buildPath = (root, resStr) = > {
if(! root.left && ! root.right){ resStr += root.val res.push(resStr)return
}

resStr += root.val + '- >'
if(root.left){
buildPath(root.left, resStr)
}
if(root.right){
buildPath(root.right, resStr)
}
}
buildPath(root, ' ')
return res
};
Copy the code``````

Complexity analysis

• Time complexity: O(N), where N indicates the number of nodes. In the depth-first search, each node will be accessed once and only once, and the path variable will be copied each time. The time cost is O(N), so the time complexity is O(N).
• Space complexity: O(N), where N indicates the number of nodes. In addition to the answer array we need to consider the stack space for recursive calls. In the worst case, when each node in the binary tree has only one child node, that is, the whole binary tree is a chain, the number of recursive levels is N, the space complexity of the sum of the space cost of path variables at each level is O(N), in the best case, when the binary tree is a balanced binary tree, its height is logN, The space complexity is O(logN)2).

(5) Symmetric binary trees

Given a binary tree, check whether it is mirror symmetric. For example, a binary tree [1,2,2,3,4,4,3] is symmetric.

``````    1
/ \
2   2/ \ \3  4 4  3
Copy the code``````

But the following one [1,2,2,null,3,null,3] is not mirrored :5r

``````    1
/ \
2   2
\   \
3    3
Copy the code``````

Advanced: Can you solve this problem recursively and iteratively?

The idea of recursion is relatively simple. The specific implementation idea is as follows:

• The left subtree of the left subtree is equal to the right subtree of the right subtree
• If the left or right node is null, the corresponding right or left node is compared for null, returning true, otherwise false
• If the left and right nodes are not empty, the left node of the left node and the right node of the right node are determined to be equal
• If they are, pass in the children of the node for recursion, otherwise return false

The iterative method needs to be implemented with the help of queues. The specific implementation idea is as follows: Through the method of “moving” two Pointers synchronously to traverse the tree, l pointer and r pointer point to the root of the tree at the beginning, then when L moves right, R moves left, and when L moves left, r moves right. Each time, check whether the values of the current l and r nodes are equal. If so, check whether the left and right subtrees are symmetric.

``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {boolean}* /

// Iteration implementation
const isSymmetric = (root) = > {
if(! root)return true
let queue = [root.left, root.right]
while (queue.length > 0) {
let node1 = queue.shift(), node2 = queue.shift()
if (node1 === null && node2 === null) continue
if (node1 === null || node2 === null|| node1.val ! == node2.val)return false
queue.push(node1.left, node2.right, node1.right, node2.left)
}
return true
}

// Recursive implementation
var isSymmetric = function(root) {
if(! root){return true
}
return isSameTree(root.left, root.right)
};

const isSameTree = (l, r) = > {
if(! l)return r === null
if(! r)return l === null

if(l.val ! == r.val)return false
return isSameTree(l.left, r.right,) && isSameTree(l.right, r.left)
}
Copy the code``````

Complexity analysis of recursive implementation:

• Time complexity: Here the tree is traversed, and the asymptotic time complexity is O(n), where n is the number of nodes in the tree.
• Space complexity: Here the space complexity is related to the stack space used for recursion, where the number of recursion levels does not exceed N, so the progressive space complexity is O(n).

Complexity analysis of iterative implementation:

• Time complexity: Here the tree is traversed, and the asymptotic time complexity is O(n), where n is the number of nodes in the tree.
• Spatial complexity: Here, a queue is needed to maintain nodes. Each node can enter and exit the queue once at most. The queue cannot exceed N points at most, so the progressive spatial complexity is O(n).

(6) The average value of the layers of the binary tree

Given a non-empty binary tree, return an array of the average values of the nodes at each level. Example 1:

``````Input:3
/ \
9  20
/  \
15   7Output:3.14.5.11[Explanation: No0The average of the layers is3In the first1Layer is14.5In the first2Layer is11. So return [3.14.5.11].Copy the code``````

Tip: Node values are in the range of 32 bit signed integers.

This is a fairly simple problem, which is sequential traversal of a binary tree. BFS (breadth-first traversal) is used to queue node values at each level and then stack and add all values. Divided by the queue length of the current layer is the average for this layer. Put it in the result. Repeat the steps until you have traversed the entire binary tree and returned the final result.

``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number[]}* /
var averageOfLevels = function(root) {
if(! root){return[]}const res = []
const queue = []

queue.push(root)

while(queue.length){
const len = queue.length
let sum = 0
for(let i = 0; i < len; i++){
const cur = queue.shift()
sum += cur.val
if(cur.left){
queue.push(cur.left)
}
if(cur.right){
queue.push(cur.right)
}
}
res.push(sum / len)
}
return res
};
Copy the code``````

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the binary tree. Breadth first search requires one visit per node, and the time complexity is O(n). We need to calculate the average for each layer of the binary tree, and the time complexity is O(h), where h is the height of the binary tree, and in any case h≤n. So the total time complexity is order n.
• Space complexity: O(n), where n is the number of nodes in the binary tree. The space complexity depends on the queue cost, and the number of nodes in the queue cannot exceed N.

(7) Right view of the binary tree

Given a binary tree, imagine yourself standing on the right side of it and return the values of the nodes visible from the right, in order from top to bottom. Example:

``````Input:1.2.3.null.5.null.4] Output: [1.3.4] :1< -- - / \2     3< -- - \ \5     4       <---
Copy the code``````

For binary tree problems, the most commonly used methods are depth first walk (DFS) and breadth first walk (BFS). Let’s use these two methods to solve this problem.

DFS:

• Set a level to hold the level of the currently-traversed binary tree, starting at 0
• Since we need to return the values of the nodes in the right view, we first iterate over the values of the right node and save the right node in the result array
• And then we go through the left node
• When the length of the resulting array is the same as the current level of the binary tree, the current node value is saved
• Repeat the steps until you have traversed all nodes of the binary tree

BFS: Use breadth-first traversal to traverse the binary tree, which is equivalent to the sequential traversal of the binary tree. For the traversal result of each layer, take the last one, here we use queue to process.

• Initializes a queue, adding the root node to the queue
• When the queue is not empty, the elements of the queue are dequeued and the last element is added to the result array
• The left and right child nodes of the element are added to the queue as the element exits the queue
• Repeat steps 2 and 3 above until the queue is empty **
``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number[]}* /

// Implementation of DFS:
var rightSideView = function(root) {
if(! root)return []
let res = []
dfs(root, 0, res)
return res
};

function dfs(root, level, res){
if(root){
if(res.length === level){
res.push(root.val)
}

dfs(root.right, level+1, res)
dfs(root.left, level+1, res)
}
}

// BFS implementation:
var rightSideView = function(root) {
if(! root)return []
let res = []
let queue = [root]
while(queue.length > 0) {let len = queue.length

while(len){
let node = queue.shift()
if(len === 1){
res.push(node.val)
}
if(node.left){
queue.push(node.left)
}
if(node.right){
queue.push(node.right)
}
len--
}
}
return res
};
Copy the code``````

DFS complexity analysis:

• Time complexity: O(n). Where n is the number of nodes in the binary tree, and depth first search accesses each node at most once, so it is linear complexity.
• Space complexity: O(n). Where n is the number of nodes in the binary tree, and in the worst case, the stack will contain the number of nodes close to the height of the tree, taking up O(n).

BFS complexity analysis:

• Time complexity: O(n). Where n is the number of nodes in the binary tree, and each node enters the queue once and leaves the queue once at most, so the complexity of breadth-first search is linear.
• Space complexity: O(n). Where n is the number of nodes in the binary tree, and each node enters the queue at most once, so the queue length cannot exceed N at most, so the space cost here is O(n).

(8) Number of nodes of a complete binary tree

Given the root node of a complete binary tree, find the number of nodes in the tree.

The definition of a complete binomial tree is as follows: In a complete binomial tree, the number of nodes at each layer reaches the maximum except that the lowest node may not be filled, and the nodes at the lowest layer are concentrated at several positions on the leftmost of the layer. If the bottom layer is Layer H, this layer contains one or two nodes.

Example 1:

``````Enter: root = [1.2.3.4.5.6] output:6
Copy the code``````

Example 2:

``````Input: root = [] Output:0
Copy the code``````

Example 3:

``````Enter: root = [1] output:1
Copy the code``````

Tip:

• The number of nodes in the tree ranges from`[0, 5 * 10]`
• `0 <= Node.val <= 5 * 10`
• The title data guarantees that the input tree is a full binary tree

Advanced: Traversing the tree to count nodes is a simple O(n) solution. Can you design a faster algorithm?

For this problem, we can use a depth-first or breadth-first walk to calculate the number of nodes in the binary tree.

1) depth-first traversal: Depth-first traversal is very simple. The passed binary tree needs to be returned, so we can directly recursively calculate the number of nodes in the binary tree:

• If the subtree is empty, the number of nodes is 0
• If the subtree has left subtree or right subtree, then the number of nodes +1, continue to recurse to find the number of left subtree nodes and right subtree nodes respectively

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the binary tree, we need to traverse the whole binary tree once;
• Space complexity: O(h), where H is the height of the binary tree, and the time complexity of recursion is O(h).

2) Breadth-first traversal: Breadth-first traversal usually initializes a pair to save the nodes of the current layer and operates on the nodes of the current layer. In this case, all we need to do is add one as the node enters the queue.

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the binary tree, we need to traverse the whole binary tree once;
• Space complexity: O(n), where n is the length of the queue, we need to put each layer in the queue.

3) Dichotomy The time complexity of the above two methods is O(n), and the time complexity will be reduced by using dichotomy.

As we know, for a complete binomial tree, all its subtrees are complete binomial trees, and some subtrees are full binomial trees. The calculation formula of the number of nodes of full binomial tree is as follows: 2-1, where H is the height of the current tree.

What makes a full binary tree? Well, we know that in a binary tree there is a concept of the depth of the tree, which is the number of edges that the root node goes through to get to that node, so we just need to determine whether the height of the left and right subtrees is the same to determine whether the current tree is a full binary tree.

If it’s not a full binary tree, it’s a smaller full binary tree, and we recurse.

Complexity analysis:

• Time complexity: each recursive call corresponds to a tree height, call logN times, each call to calculate the height of the full binary tree requires O(logN), so the time complexity is O(logN).
• Space complexity: O(1), we only need to maintain a limited amount of extra space.

``````/** * 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 countNodes = function(root) {
if(! root){return 0
}

let queue = [root]
let res = 1
while(queue.length){
let node = queue.shift()
if(node.left){
queue.push(node.left)
res++
}
if(node.right){
queue.push(node.right)
res++
}
}
return res
};
Copy the code``````

Depth first traversal:

``````/** * 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 countNodes = function(root) {
if(! root){return 0
}
return 1 + countNodes(root.left) + countNodes(root.right)
}
Copy the code``````

Dichotomy:

``````/** * 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 countNodes = function(root) {
if(! root){return 0
}

let leftHeight = 0, rightHeight = 0
let leftNode = root, rightNode = root

while(leftNode){
leftHeight++
leftNode = leftNode.left
}
while(rightNode){
rightHeight++
rightNode = rightNode.right
}

if(leftHeight === rightHeight){
return 2 ** leftHeight - 1
}
return 1 + countNodes(root.left) + countNodes(root.right)
};
Copy the code``````

(9) The sum of the left leaves

Calculates the sum of all the left leaves of a given binary tree. Example:

``````3
/ \
9  20
/  \
15   7
Copy the code``````

In this binary tree, we have two left leaves, 9 and 15, so we return 24

For this problem, we can sequence through the binary tree, initialize a pair queue to hold the elements at the current level, walk through the elements in the queue, if the left subtree of that node does not exist, it is a left leaf node, and add that to the result.

``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number}* /
var sumOfLeftLeaves = function(root) {
if(! root)return 0
let res = 0
const queue = [root]

while(queue.length){
const cur = queue.shift()
if(cur.left){
if(! cur.left.left && ! cur.left.right){ res += cur.left.val } queue.push(cur.left) }if(cur.right){
queue.push(cur.right)
}
}
return res
};
Copy the code``````

Complexity analysis:

• The time complexity is O(n). In the worst case, the binary tree has only the right subtree, but in the case of a linked list, we need to traverse the entire binary tree. The time complexity is O(n).
• Space complexity: O(n), where n represents the length of the queue, which is always less than or equal to the number of nodes in the binary tree.

(10) Find the value in the lower left corner of the tree

Given a binary tree, the leftmost value is found in the last row of the tree. Example 1:

``````Input:2
/ \
1   3Output:1
Copy the code``````

Example 2:

``````Input:1
/ \
2   3/ / /4   5   6
/
7Output:7
Copy the code``````

Note: You can assume that the tree (that is, the given root node) is not NULL.

You can do sequential traversal of the binary tree, and sequential traversal is based on breadth-first traversal.

In the process of traversal, we initialize a queue to hold the nodes of the current layer. In this process, we need to first add the right child node of the root node to the queue, and then add its left child node to the queue.

In this process, the column elements are queued and added to the RES array, so that the last value of the array is the value in the lower left corner of the binary tree.

``````/** * 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 findBottomLeftValue = function(root) {
const queue = [root]
let res = []

while(queue.length){
const node = queue.shift()
res.push(node.val)
node.right && queue.push(node.right)
node.left && queue.push(node.left)
}
return res[res.length - 1]};Copy the code``````

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the binary tree, we need to traverse the whole tree;
• Space complexity: O(n), where n is the height of the binary tree, we need to initialize an array to hold all the nodes of the binary tree;

(11) The most binary tree

Given an integer array nums with no repeating elements. A maximum binary tree built directly recursively from this array is defined as follows:

1. The root of a binary tree is an array`nums`The largest element in.
2. The left subtree is the largest binary tree constructed recursively from the left part of the maximum value in the array.
3. The right subtree is the largest binary tree constructed recursively from the part to the right of the maximum value in the array.

Returns the largest binary tree built with the given array NUMs.

Example 1:

``Input: nums = [3.2.1.6.0.5] Output: [6.3.5.null.2.0.null.null.1] Explanation: The recursive call is as follows: - [3.2.1.6.0.5] is6, the left part is [3.2.1], the right part is [0.5]. - [3.2.1] is3The left part is [] and the right part is [].2.1]. - An empty array with no child nodes. - [2.1] is2The left part is [] and the right part is [].1]. - An empty array with no child nodes. - There is only one element, so the child node is a value of1The node. - [0.5] is5, the left part is [0], the right part is []. - There is only one element, so the child node is a value of0The node. - An empty array with no child nodes.Copy the code``

Example 2:

``````Input: nums = [3.2.1] Output: [3.null.2.null.1]
Copy the code``````

Tip:

• `1 <= nums.length <= 1000`
• `0 <= nums[i] <= 1000`
• `nums`All integers inEach other is not the same

We use recursion to implement this problem directly:

• First, get the largest value in the array to use as the current root node
• Gets the array element on the left and the array element on the right of the maximum value in the array
• Use the two arrays to recursively build the left and right subtrees of the binary tree
``````/** * 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 {number[]} nums
* @return {TreeNode}* /
var constructMaximumBinaryTree = function(nums) {
if(nums.length === 0) {return null
}

let max = Math.max(... nums)let root = new TreeNode(max)
let leftArray = nums.slice(0, nums.indexOf(max))
let rightArray = nums.slice(nums.indexOf(max) + 1)

root.left = constructMaximumBinaryTree(leftArray)
root.right = constructMaximumBinaryTree(rightArray)

return root
};
Copy the code``````

Complexity analysis:

• Time: O(n), recursion n times. Each time you recursively search 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).
• Space complexity: O(n). The recursive call depth is n. On average, an array of length n recurses to a depth of O(logn).

(12) The same tree

Given two binary trees, write a function to check that they are the same. Two trees are considered the same if they are structurally identical and the nodes have the same values.

Example 1:

``````Input:1         1/ \ \2   3     2   3

[1.2.3],   [1.2.3] output:true
Copy the code``````

Example 2:

``````Input:1          1
/           \
2             2

[1.2],     [1.null.2] output:false
Copy the code``````

Example 3:

``````Input:1         1/ \ \2   1     1   2

[1.2.1],   [1.1.2] output:false
Copy the code``````

We just recursively go through the nodes of the two trees, see if they’re consistent, and if they are, we just return false. The depth-first traversal is used here.

``````/** * 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} p
* @param {TreeNode} q
* @return {boolean}* /
var isSameTree = function(p, q) {
if(! p && ! q){return true
}
if(p === null || q === null) {return false
}
if(p.val ! == q.val){return false
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};
Copy the code``````

Complexity analysis:

• Time complexity: O(min(m,n)), where m and n are nodes of the two binary trees respectively. Depth first search is carried out for two binary trees at the same time. Only when the corresponding nodes in the two binary trees are not empty will the node be accessed, so the number of nodes accessed will not exceed the number of nodes in the smaller binary tree.
• Space complexity: O(min(m,n)), where m and n are nodes of the two binary trees respectively. The spatial complexity depends on the number of layers of recursive calls, which do not exceed the maximum height of a smaller binary tree, which in the worst case is equal to the number of nodes.

(13) The most frequently occurring subtree elements and

Given the root of a binary tree, I ask you to find the sum of the most frequent subtree elements. The “sum of subtree elements” of a node is defined as the sum of the elements of all nodes (including the node itself) in the binary tree at the root of the node.

You need to return the most frequently occurring subtree elements and. If more than one element occurs the same number of times, return all the elements of the subtree with the most occurrences (in no order). Example 1:

``````Input:5
/  \
2   -3Return to the [2, -3.4], all values appear only once, and all values are returned in any order.Copy the code``````

Example 2:

``````Input:5
/  \
2   -5Return to the [2], only2It appears twice, minus5Only appear1Times.Copy the code``````

Tip: Assume that any subtree element and can be represented as a 32-bit signed integer.

This problem is the same as the mode problem of binary trees:

• First, we iterate through the tree, finding the sum of the subtrees of all the nodes
• A map is used to record the number of occurrences of each element during the traversal
• After the traversal is complete, traverse the map to find the sum with the most times and put it in the RES
``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number[]}* /
var findFrequentTreeSum = function(root) {
let map = {}, res = [], max = 0

const calcuSum = (root) = > {
if(! root){return 0
}
let left = calcuSum(root.left)
let right = calcuSum(root.right)

let sum = left + right + root.val
// Assign the current node to the sum of all its children for later calculation
root.val = sum
map[sum] ? map[sum] += 1 : map[sum] = 1
return root.val
}
calcuSum(root)

for(let key in map){
if(map[key] === max){
res.push(key)
}
if(map[key] > max){
max = map[key]
res = [key]
}
}
return res
};
Copy the code``````

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the tree, we need to traverse the whole tree to find the sum of the subtrees of each node.
• Space complexity: O(n), where n is the number of nodes in the tree, and what is required here is the space cost of the recursive stack space.

(14) The maximum width of the binary tree

Given a binary tree, write a function to get the maximum width of the tree. The width of the tree is the maximum width of all the layers. This binary tree has the same structure as a full binary tree, but some nodes are empty.

The width of each layer is defined as the length between two endpoints (the leftmost and rightmost non-empty nodes of the layer, and the null nodes between the endpoints are also counted as length). Example 1: * *

``````Input:1
/   \
3     2
/ \     \
5   3     9Output:4Explanation: The maximum occurs at the end of the tree3Layer, width is4 (5.3.null.9).Copy the code``````

Example 2:

``````Input:1
/
3
/ \
5   3Output:2Explanation: The maximum occurs at the end of the tree3Layer, width is2 (5.3).Copy the code``````

Example 3:

``````Input:1
/ \
3   2
/
5Output:2Explanation: The maximum occurs at the end of the tree2Layer, width is2 (3.2).Copy the code``````

Example 4:

``````Input:1
/ \
3   2
/     \
5       9
/         \
6           7Output:8Explanation: The maximum occurs at the end of the tree4Layer, width is8 (6.null.null.null.null.null.null.7).Copy the code``````

Note: The answers are within the representation range of 32 bit signed integers.

In this problem, we can iterate through the binary tree layer by layer, initializing a queue to hold the nodes at that level, and this queue holds the node value and index value of the current node.

We know that the index value of a node’s left subtree is twice that of its index value, that is, left = index* 2, and the index value of the right subtree is twice that of its index value, that is, right = index* 2 + 1. So the width of each layer is: right-left + 1, so the width of each layer is solved, and the maximum value is automatically solved.

In addition, we have to consider the case where the binary tree is very deep, and the index may exceed the valid value of the number. At the end of the question, the answer is indicated to be within the range of 32 bit signed integers. In other words, the maximum width of the final answer should not exceed a 32 bit signed integer. The idea is that empty nodes are also indexed. If there are many levels, but there is only one right node per level in the use case, empty nodes cannot be counted because there is no limit to the number of levels. We can subtract the index of the first node in the same layer from the index of the node in the same layer, and then calculate the index of the child nodes, so that the index of each layer starts from 0, so as to solve the problem of large numbers.

``````/** * 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 widthOfBinaryTree = function(root) {
if(! root){return 0
}

const nodes = [{node: root, index: 0}]
let res = 0

while(nodes.length){
let len = nodes.length
const start = nodes[0].index
const end = nodes[len - 1].index
res = Math.max(res, end - start + 1)

while(len--){
let {node, index} = nodes.shift()

index -= start

node.left && nodes.push({ node: node.left, index: index * 2 })
node.right && nodes.push({ node: node.right, index: index * 2 + 1}}})return res
};
Copy the code``````

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the binary tree, we need to traverse the entire binary tree;
• Space complexity: O(n) where n is the length of the Nodes stack.

(15) The maximum depth of the binary tree

Given a binary tree, find its maximum depth. The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node. Note: A leaf node is a node with no child nodes. Example: given a binary tree [3,9,20,null,null,15,7],

``````    3
/ \
9  20
/  \
15   7
Copy the code``````

Recursive implementation: recursive binary tree node, get the left subtree and the right subtree of the maximum depth, after comparison, return the maximum depth, specific steps are as follows:

• Determine whether the binary tree is empty, empty directly return 0, end, non-empty binary tree continues
• Calculate the maximum depth of the left and right subtrees recursively respectively
• The comparison returns the maximum depth of the binary tree, based on the two numbers that return the two
``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number}* /
var maxDepth = function(root) {
if(! root){return 0;
}else{
var leftDepth = maxDepth(root.left)
var rightDepth = maxDepth(root.right)
return Math.max(leftDepth,rightDepth)+1}};Copy the code``````

Complexity analysis:

• Time complexity: O(n) : recursively queries all child nodes of the tree. The query takes order n time.
• Space complexity: O(n) : Each recursion needs to create a new temporary space, space complexity O(n).

(16) The minimum depth of the binary tree

Given a binary tree, find its minimum depth. Minimum depth is the number of nodes on the shortest path from the root node to the nearest leaf node. A leaf node is a node with no child nodes.Example 1:

``````Enter: root = [3.9.20.null.null.15.7] output:2
Copy the code``````

Example 2:

``````Enter: root = [2.null.3.null.4.null.5.null.6] output:5
Copy the code``````

Tip:

• The number of nodes in the tree ranges from`[0, 10]`
• `-1000 <= Node.val <= 1000`

** Sequence traversal implementation: set a level, indicating the current number of layers, and then the binary tree sequence traversal, each increase a layer, the level will increase one, until a node has no left or right subtree, the end of traversal, return level.

``````/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number}* /
var minDepth = function(root) {
if(! root){return 0;
}
var level = 0;
var queue = [root];
while(queue.length){
level += 1;

var len = queue.length;
while(len--){
var node = queue.shift();
if(! node.left&&! node.right){return level;
}
if(node.left){
queue.push(node.left);
}
if(node.right){ queue.push(node.right); }}}return level;
};
Copy the code``````

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the tree. Each node is accessed once.
• Space complexity: O(n), where n is the number of nodes in the tree. The spatial complexity depends primarily on the cost of the queue, the number of elements in the queue does not exceed the number of nodes in the tree.

(17) Balanced binary tree

Given a binary tree, determine whether it is a highly balanced binary tree. In this case, a height-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 is no more than 1.

Example 1:

``````Enter: root = [3.9.20.null.null.15.7] output:true
Copy the code``````

Example 2:

``````Enter: root = [1.2.2.3.3.null.null.4.4] output:false
Copy the code``````

Example 3:

``````Input: root = [] Output:true
Copy the code``````

Complexity analysis:

• The number of nodes in the tree is in the range [0, 5000]
• -10<= Node.val <= 10