Brush these 30 trees, probably still hand tear not big factory interview

preface

Some guy said that he was almost done with all the trees, and I found these things… , and I as a chef who is committed to the world’s best writing algorithm front end, always brush a part of the problem, there is a little discovery, now we will talk about, dish chicken such as I, found what.

The body of the

A lot of big guys recommend that we start with trees, and then quit with trees, so why are trees so important — I don’t know, because I’m not a big guy;

But in front of really use a lot of knowledge in related to tree, for example a DOM tree, the Diff algorithm, including the prototype chain is actually a tree, tree, actually to learn the knowledge or have bigger help, of course we still have to consider the learning algorithm, and the tree just is one big key – at least on the front end.

The main reason is that the tree is gaudy, compared to the lower liba people, need to abstract but also can draw out not to let you have no clue, simply speaking, it looks very strong, but in fact is also very grounded, commonly known as more general; Do you know the front interview algorithm, take an examination of is not you have active learning ability, abstract ability, etc., but considering the jagged front the entertainment circle, exam difficult it may be all the cracks, so as to screen out fish, but also cannot too advanced, the tree is the relatively modest, so quickly to brush up my friends;

Here is originally to follow the 3:5:2 difficulty to brush, is expected to brush 30 questions is about the same, but the actual medium problem brush can not stop, the problem is to die, easy problem is like chewing wax, so XDM bear. Topic selection is mainly the man’s choice of examples and Leetcode HOT topics and byte topics, in general representative or enough, brush should probably be able to deal with the tree algorithm.

If you feel that it is a little help, please click a like to leave a message, more than 10 likes to update the next part; Well, even though it will be updated, is so smelly shameless, big guy come on, Ori give!!

Traversal of a binary tree

The recursive traversal

1. When you recurse, you can just do all the front, middle and back
2. Recursion is one of the easiest ways to do sequential traversal and one of the easiest ways to figure it out, but if you don’t, just draw a picture

Iterative traversal — Two-color notation

1. Use color to mark node states, new nodes in white and already visited nodes in gray — you can use numbers or any other label
2. If the node encountered is white, it is marked gray, and the right node, itself, and the left node are pushed once — in order traversal
3. If the node encountered is gray, the node is printed out
4. Notice that we’re using the stack, so it’s last in, first out, so if it’s a middle-order traversal, left-middle-right, then it’s going to be right-middle-left when you insert the stack

According to the man’s instructions, we will use normal recursive do good, as if we do not sorting problem order, it is a good sort, but once the interviewer asked in another iteration way, we will set a template, rather than to remember multiple iterations of writing simple, after all memory capacity is limited, and the subsequent to traverse the iterative method is really quite pit, Save whatever memory you can

144. Preorder traversal of a binary tree

// 144. Binary tree preorder traversal

/** * @ analysis -- recursion */
var preorderTraversal = function (root) {
  const ret = [];
  const recursion = (root) = > {
    if(! root)return;
    ret.push(root.val);
    recursion(root.left);
    recursion(root.right);
  };
  recursion(root);
  return ret;
};

/** * @analysis -- Iteration -- two-color labeling * 1. Use color to mark node states, new nodes are white, already visited nodes are gray -- you can use a number or any other label * 2. If the node encountered is white, mark it as gray, and push the right node, itself, and left node once -- in order traversal * 3. If the node is gray, output the node * 4. Note that this is stored on the stack, so it is last in first out, this is preorder traversal, middle-left-right, so when inserting the stack, it is reversed right-left-center */
var preorderTraversal = function (root) {
  const ret = [];
  const stack = [];
  stack.push([root, 0]); // 0 is white and untreated, 1 is gray and treated
  while (stack.length) {
    const [root, color] = stack.pop();
    if (root) {
      if (color === 0) {
        // If a white ball is encountered, insert -- preorder
        stack.push([root.right, 0]);
        stack.push([root.left, 0]);
        stack.push([root, 1]);
      } else {
        // When a gray ball is encountered, the net is drawnret.push(root.val); }}}return ret;
};

Copy the code

1.94 Binary tree in order traversal

// 94. In-order traversal of binary trees

/** * @ * 1. * 2. * 2. Recursion is one of the easiest ways to do sequential traversal and the easiest way to understand it, but if you don't, just draw a graph */
var inorderTraversal = function(root) {
    const ret  = []
    const recursion = root= > {
        if(! root)return
        recursion(root.left)
        // This is the middle order, so between two recursions, if the preorder is in front, then the posterior order is in the back
        ret.push(root.val)
        recursion(root.right)
    }
    recursion(root)
    return ret
};

/** * @analysis -- Iteration -- two-color labeling * 1. Use color to mark node states, new nodes are white, already visited nodes are gray -- you can use a number or any other label * 2. If the node encountered is white, mark it as gray, and push the right node, itself, and left node once -- in order traversal * 3. Note that this is stored on the stack, so it is last in, first out, so if it is in order traversal, left - middle - right, then insert the stack in reverse right - middle - left */
var inorderTraversal = function(root) {
    const ret  = []
    const stack = []
    stack.push([root,0]) // 0 is white and untreated, 1 is gray and treated
    while(stack.length) {
        const  [root,color] = stack.pop()
        if(root){
            if(color === 0) {// If a white ball is encountered, insert -- in order traversal
                stack.push([root.right,0])
                stack.push([root,1])
                stack.push([root.left,0])}else{
                // When a gray ball is encountered, the net is drawn
                ret.push(root.val)
            }
        } 
    }
    return ret
};
Copy the code

Back-end traversal of a binary tree

// 145. Back-end traversal of binary tree

/** * @ analysis -- recursion */
var postorderTraversal = function(root) {
    const ret = []
    const dfs = (root) = > {
        if(! root)return 
        dfs(root.left)
        dfs(root.right)
        ret.push(root.val)
    }
    dfs(root)
    return ret
};

/** * @analysis -- iteration -- bicolor ball */
var postorderTraversal = function(root) {
    const ret = []
    const stack = []
    stack.push([root,0])
    while(stack.length){
        const [root,color] = stack.pop()
        if(root) {
            if(color === 0){
                stack.push([root,1])
                stack.push([root.right,0])
                stack.push([root.left,0])}else{
                ret.push(root.val)
            }
        } 
    }
    return ret
}
Copy the code

Brush the process of some confusion

Top down (preorder traversal) and bottom up (subsequent traversal)

These two nouns often appear in many problems about trees, and where is the correlation point when we iterate the tree evaluation? After slowly brushing the problems, I found that although DFS has three forms, when abstract to specific problems, they actually belong to different methods.

For preorder traversal, is the first to get to the root node of the information, and then do some coding, after traversal down again, this way of traverse is called top-down thinking, we begin from the root node, can carry a certain information, continue downwards traversed, processing first, get a temporary results, to the top of the node as the information;

In the case of top-down traversal, when you get to the root node, you end up processing all the nodes, and you get the expected result, so when you do a preorder traversal, you declare a global variable, and then when you’re done, you return that value.

Example :563. The slope of a binary tree

Analysis of the1.Return the sum of the subtree values from the bottom up, and then find the corresponding slope, and add up.2.It is important to note that the sum value of the left and right subtrees is uncertain, so the absolute value should be used3.Time complexity ${O(N)}$var findTilt = function (root) {
  let ret = 0;
  const recursion = (root) = > {
    if(! root)return 0;
    const left = recursion(root.left);
    const right = recursion(root.right);
    ret += Math.abs(left - right);
    return left + right + root.val;
  };
  recursion(root);
  return ret;
};
Copy the code

In the case of post-order traversal, you want to traverse the leaf nodes and then process the root nodes up, which is called bottom-up;

In fact, the bottom-up is a recursive approach, you pass it to the leaves, you return a certain value, you come back, and then you do the rest of the processing based on the value of the subtree, so don’t get confused by the traversal, the traversal doesn’t just end, it just started.

Instead of using DFS, use recursion directly when handling bottom-up problems.

Example:

Judge traversal to the boundary, what judge at the leaf node, when run directly to null return?

When we do DFS traversal, we need to traverse the leaves, and then do the final processing, some problems we see is null/0, and so on; Sometimes we just decide whether a leaf node, if(! root.left && ! Root. Right);

This is in the process of brush question feel te confusing place, in the beginning, I like to use null, because it write less, and by the way, could you put the root node is empty border also did, recently brush when I began to feel a little bit judgment node will be more safe, and don’t have to do further processing, until I write again 👆 words, a little thought

When we use bottom-up, even null is useful because we need to return the value from the child node, so using null is basically OK.

Example: 104. Maximum depth of a binary tree

/** * 1. From top to bottom, with a layer number parameter, judged as leaf node to determine the maximum value */
var maxDepth = function (root) {
  if(! root)return 0;
  let ret = 0;
  const dfs = (root, depth) = > {
    if (root.left) dfs(root.left, depth + 1);
    if (root.right) dfs(root.right, depth + 1);
    ret = Math.max(ret, depth);
    return;
  };
  dfs(root, 1);
  return ret;
};

// From low to high
var maxDepth = function (root) {
  const dfs = (root) = > {
    if(! root)return 0;
    return Math.max(dfs(root.left), dfs(root.right))+1;
  };
  return dfs(root);
};

Copy the code

However, in some cases that carry data and evaluate from top to bottom, if the traversal ends at NULL, it is easy to repeat the calculation error, and since there is no need to get the return value, I recommend using the method of judging the node in this case.

Example :1022. Sum of binary numbers from root to leaf

/** * @analysis * 1. Find the current number of each path from top to bottom and save it in the input parameter * 2. Add the values to the leaves node * 3. It is important to process the values on the leaves node, not on the null node, otherwise */ will be computed twice
 var sumRootToLeaf = function(root) {
    // if(! Root) return 0 // They know that the nodes are 1-1000
    let ret = 0
    const dfs = (root,sum) = > {
        const temp = (sum<<1) + root.val
        if(! root.left && ! root.right){ ret +=tempreturn 
        }
        if(root.left) dfs(root.left,temp)
        if(root.right) dfs(root.right,temp)
    }

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

Topic summary

A simple question

• 101. Symmetric binary trees
• The maximum depth of a binary tree
• 226. Flip the binary tree
• 563. Slope of a binary tree
• Sum of binary numbers from roots to leaves
• Minimum distance between nodes in binary search tree

The medium topic

• Maximum width of binary tree
• Flip the binary tree to match preorder traversal
• 863. All nodes of distance K in a binary tree
• Interview question 04.06. Successors
• Verify the binary search tree
• Restore binary search tree
• 222. Number of nodes in a complete binary tree
• Interview question 04.12. Sum up paths
• Find the sum of the numbers from the root node to the leaf node
• Count the number of good nodes in the binary tree
• Binary tree pruning
• Remove the leaf node for the given value
• The maximum difference between a node and its ancestor
• 865. The smallest tree with all deepest nodes
• Number of good leaf node pairs
• 894. All possible full binary trees
• 96. Different binary search trees
• 437. Total path III

Difficult question

• Vertical order traversal of binary trees
• 37. Serialize the binary tree
• 124. Maximum sum of paths in a binary tree
• 834. Sum of distances in the tree

A simple question

101. Symmetric binary trees

Analysis of the

1. Symmetric binary tree, in fact, requires mirror alignment, so the recursion process requires at least two root nodes, and then DFS is mainly to determine whether the two trees are symmetric
2. Here is the top-down assignment of the subtree nodes compared to each other, left and right, and the bottom-up return of the final result
3. In a given DFS, if both sides of the comparison are null, then the comparison is symmetric. Return false if only one side has a value, or if both sides have a value but the values are different;
4. Each recursion is a comparison of left and right outer layers, left and right inner layers
5. Time complexity: O(h){O(h)}O(h), where h is the height of the tree

// 101. Symmetric binary trees
var isSymmetric = function (root) {
  if(! root)return false;
  const dfs = (left, right) = > {
    if(! left && ! right)return true;
    if(! left || ! right || left.val ! == right.val)return false;
    return dfs(left.left, right.right) && dfs(left.right, right.left);
  };
  return dfs(root.left, root.right);
};
Copy the code

The maximum depth of a binary tree

• There are three ways to search using trees, sequential, top down DFS, and bottom up recursive DFS

Sequence traversal

1. No matter the depth, the number of layers, etc., we can directly find the last leaf node of the last layer by sequence traversal
2. Time complexity O (N) (N)} {O O (N), space complexity O (K) (K)} {O O (K), K is the maximum width

// 104. The maximum depth of the binary tree

/** * 1. */ ** * 2

var maxDepth = function (root) {
  if(! root)return 0;
  let ret = 0;
  const queue = [];
  queue.push(root);
  while (queue.length) {
    ret++; // Enter the first floor
    let len = queue.length;
    while (len--) {
      // Sequence traversal
      const root = queue.shift();
      if (root.left) queue.push(root.left);
      if(root.right) queue.push(root.right); }}return ret;
};
Copy the code

DFS — top down

1. So when we calculate the number of levels, we can think about it, if we don’t go through a level, we take a parameter, and that parameter is a marker, so for example, this is depth
2. So that when we get to the leaves, we can compare it to the maximum, and then we can finish the route
3. Time complexity O (N) (N)} {O O (N), space complexity O (D) (D)} {O O (D), D is the depth

/** * 1. From top to top, with a layer number parameter, determine the leaf node to determine the maximum value */
var maxDepth = function (root) {
  if(! root)return 0;
  let ret = 0;
  const dfs = (root, depth) = > {
    if (root.left) dfs(root.left, depth + 1);
    if (root.right) dfs(root.right, depth + 1);
    // When you get to this point, it turns out to be a leaf node, so take the maximum and end this time
    ret = Math.max(ret, depth);
  };
  dfs(root, 1);
  return ret;
};
Copy the code

Recursion — from bottom to top

• If you have top down, then of course you have bottom up;
• The method name is recursion, which requires DFS to reach the bottom and then return to the root node.
• From top to bottom, the depth is calculated from the root node to the leaf node; From the bottom up the reverse, run to the bottom, and then continue to find the maximum depth of the leaves, but add itself back to the top
• Time O(N){O(N)}O(N), space O(1){O(1)}O(1)

// From low to high
var maxDepth = function (root) {
  const recursion = (root) = > {
    // It's just at the bottom, so the height is 0
    if(! root)return 0;
    // The height of each node is the maximum height of the tree of two nodes + the height of the layer in which the node is located
    return Math.max(recursion(root.left), recursion(root.right)) + 1;
  };
  return recursion(root);
};
Copy the code

226. Flip the binary tree

Analysis — bottom up

• Because we’re going to reverse the binary tree, we’re going to do the same thing for any subtree, so we can just pass it to the leaves and start flipping
• You pass the flipped subtree from the bottom to the top node, until you get to the root node, and you get two flipped trees, and then you switch places
• Time complexity O(N){O(N)}O(N)

// 226. Flip the binary tree
var invertTree = function (root) {
  const dfs = (root) = > {
    // Return null when the bottom is reached
    if(! root)return null;
    // 1. Recursively obtain the left and right subtrees after flipping
    const left = dfs(root.left);
    const right = dfs(root.right);
    // 2. Reverse the positions of the two trees
    root.left = right;
    root.right = left;
    // Finally return the tree after the reversal
    return root;
  };
  return dfs(root);
};
Copy the code

563. Slope of a binary tree

Analysis of the

1. Return the sum of the subtree values from the bottom up, and then find the corresponding slope, and add up.
2. It is important to note that the sum value of the left and right subtrees is uncertain, so the absolute value should be used
3. Time complexity O(N){O(N)}O(N)

var findTilt = function (root) {
  let ret = 0;
  const recursion = (root) = > {
    if(! root)return 0;
    const left = recursion(root.left);
    const right = recursion(root.right);
    ret += Math.abs(left - right);
    return left + right + root.val;
  };
  recursion(root);
  return ret;
};
Copy the code

Sum of binary numbers from roots to leaves

Analysis of the

1. Figure out the current number of each path from the top down and save it in the input parameter
2. Add up the values at the leaves
3. It is important to process it in the leaf node, not in the null node, otherwise it will double count

var sumRootToLeaf = function(root) {
    // if(! Root) return 0 // They know that the nodes are 1-1000
    let ret = 0
    const dfs = (root,sum) = > {
        const temp = (sum<<1) + root.val
        if(! root.left && ! root.right){ ret +=tempreturn 
        }
        if(root.left) dfs(root.left,temp)
        if(root.right) dfs(root.right,temp)
    }

    dfs(root,0)
    return ret

};
Copy the code

Minimum distance between nodes in binary search tree

Analysis of the

1. So this is a lesson in binary search tree BST, where you just slap your head and you want to do a middle order traverse, and you get a single increment
2. Use a variable to hold the first value of the sequence traversal in the BST; Use a global variable to hold the minimum difference
3. Time complexity O(N){O(N)}O(N)

var minDiffInBST = function(root) {
    let ret = Infinity
    let prev = undefined // Save the previous value
    const dfs = (root) = > {
        if(! root)return
       dfs(root.left)
        // Do it here
        if(prev === undefined) {// The first value, since the difference requires two values, is equivalent to initialization
            prev = root.val
        }else{
            ret = Math.min(ret,root.val-prev)
            prev = root.val
        }
        dfs(root.right)
    }
    dfs(root)
    return ret
};
Copy the code

The medium topic

Maximum width of binary tree

Analysis – based on the properties of complete binary trees

1. To find the width, blind guess sequence traversal is appropriate, but when to add null is decent
2. There is a point of reduction — the left-most and right-most non-empty nodes of the layer, and the null nodes between the two endpoints are also counted in the length — that is, when traversing a layer where there are nodes, the first node must exist, and so must the last node
3. Although the left node is determined, the right node size is uncertain. How many nulls exist in the middle and whether there is a node separated by n nulls are uncertain. In this case, consider the tree as a full binary tree, and then all nodes have a POS attribute
4. We take 1 as pos of root node, the left node is 2n, and the right node is 2n+1
5. Note that since the value of pos increases exponentially, that is, 2^k, where K is the depth of the tree, we also know that the accuracy will be lost after 2^53,
6. The width of the first 53 layers is 1, so we need to start from the 54th layer. But at this time, pos is already beyond the limit of JS Number type
7. In this case, we consider using BigInt as the value of pos node, but because the numeric type and the large type can not be calculated, so the final evaluation, we need to perform the corresponding conversion.

// 662. Maximum width of binary tree
var widthOfBinaryTree = function (root) {
  const queue = [];
  queue.push([root, 1n]);
  let max = 0;
  let steps = 0,
    curDepth = 0; // This is used to determine the first node
  let leftPos = 0n; // The position of each left node
  while (queue.length) {
    / / the layer number of + 1
    steps++;
    // If there are still layers
    let len = queue.length;
    while (len--) {
      // Start a layer of traversal
      const [root, pos] = queue.shift(); // Remove the node
      if (root) {
        // As long as there are child nodes, even if one does not exist, it must be put in the queue
        queue.push([root.left, 2n * pos]);
        queue.push([root.right, 2n * pos + 1n]);

        if(curDepth ! == steps) {// The first node
          curDepth = steps; // Update the depth at this time
          leftPos = pos; // The position of the left node
        }
        // Each existing node is updated continuously
        // Since bigInt and number are not mathematically operable, convert bigInt to a string, then implicitly convert it to a number, and then compare
        max = Math.max(max, (pos - leftPos + 1n).toString()); }}}return max;
};

Copy the code

Flip the binary tree to match preorder traversal

Analysis:

1. In my opinion, the biggest difficulty of this question is to read the question and understand the meaning of the question. First, for the concept of tree turnover, we can first go to a simple question 226. Let’s flip the binary tree.
2. The flip here involves whether the root node should flip the left and right trees, so in the traversal process, the root node must be taken as the input parameter, and then a series of logic is performed. After all, when the flip is needed, the ROOT node should be stored in RET
3. So I’m going to give you A tree A, the root node of A, and the array that V goes through first, and then I’m going to ask if A can flip the least number of n nodes so that A and V are the same. OK, so what we’re going to do is we’re going to go through the tree V, and we’re going to match the value of V to the value of A, and see if we can match the tree
4. For a traversal, we first determines the value of the root node is the same, will enter the traversal of this time, then mainly around the tree, for tree V, with pos are given according to the first sequence traversal value unceasingly, for V, you can use the left tree matching, if the match is successful, is what thing, everybody is the same; If the left tree doesn’t match, you go to the right tree first, and then you go to the left tree, in which case you have to flip the current node to make sure that the previous case of tree A matches V;
5. If there is no successful match between the left and right trees of A in the matching process, then the traversal of A will be extracted. In this case, the iteration of POS will not be finished, which is an exception, and [-1] will be returned.
6. Time complexity O(N){O(N)}O(N)

 var flipMatchVoyage = function(root, voyage) {
    if(root.val ! == voyage[0]) return [-1] // Used to judge the root node before entering DFS
    const ret = [] 
    let pos = 0 // This is used to get the value of voyage, which is also used to traverse the tree V
    const dfs = root= > {
        // Pos must be followed every time the traversal is made
        pos++ 
        // For each node, it is written according to the first order of traversal
        if(root.left && root.left.val === voyage[pos] ){
            // If the left tree ADAPTS at this node, then go ahead, because this is a preorder traversal
            dfs(root.left)
        }
        if(root.right && root.right.val === voyage[pos] ){
            dfs(root.right)
            // After the right tree is completed, we need to see if the value of pos matches the left tree, that is, if the right tree is first followed by the left tree, that is, the current root node is the node to be flipped
            if(root.left && root.left.val === voyage[pos] ){
                ret.push(root.val)
                dfs(root.left)
            }
        }
    }

    dfs(root)
    if(pos<voyage.length){
        // The voyage is stuck by the restriction before the journey is complete
        return [-1]}return ret
};
Copy the code

863. All nodes of distance K in a binary tree

Analysis of the

1. So let’s just break it down a little bitFind the node from the root node KIs it easy to find out, just take K steps from the root node
2. And by extending it a little bit,Find the child node from the node target K, it can only be found from the child nodes. The reason why this problem can be called medium is that its target is not necessarily the root node, and it can be found up;
3. For a simple binary tree, there is no way to find its parent based on the child node, just like a unidirectional linked list can not find the previous node prev based on the current node, so we can build one, think of the classic Diff algorithm, many times when we use a tree, we need to directly find the parent node, So the first step here is to make the parent pointer to the root to target node
4. Looking for, in the official start of the need to pay attention to, from bottom to up when we find the parent node as a root node, and then find the top-down process of child nodes, will have the risk of repeated values, so you need to have a variable to store up the parent node, and then every time I want to get a value under, avoid these nodes

var distanceK = function (root, target, k) {
  let targetNode = undefined;
  // The first DFS is to place the parent pointer between the root node -> target
  const setDfs = (root) = > {
    if (root === target) {
      // Stop the rest of the search if it is found
      targetNode = root;
    }
    if(root.left && ! targetNode) { root.left.parent = root; setDfs(root.left); }if (root.right && !targetNode) {
      root.right.parent = root;
      setDfs(root.right);
    }
  };
  setDfs(root);

  const ret = [];
  const paths = []; // When the parent node is fetched up, the node is passed

  // Look from top to bottom, where index is the distance from target
  const find = (root, index) = > {
    if (index === k) {
      ret.push(root.val);
    }
    if (index < k) {
      if(root.left && ! paths[root.left.val]) find(root.left, index +1);
      if(root.right && ! paths[root.right.val]) find(root.right, index +1); }};let index = 0;
  while (targetNode && index <= k) {
    // Record the parent node to be fetched up
    paths[targetNode.val] = targetNode.val;
    // Select the appropriate value from the root
    find(targetNode, index);
    targetNode = targetNode.parent;
    // Each time the node is connected, the node must be connected once
    index++;
  }

  return ret;
};

Copy the code

Interview question 04.06. Successors

Analysis of the

1. In order to iterate, save all nodes into the array, and then find P, save the next value of the index, and then after the end of the iterate, from the array
2. It’s O(N){O(N)}O(N) in time and space.

 var inorderSuccessor = function(root, p) {
    if(! root)return null
    let arr = []
    let ret = 0
    const dfs = (root) = > {
        if(! root)return 
        dfs(root.left)
        arr.push(root)
        if(root === p) {
            ret = arr.length
        }
        dfs(root.right)

    }
     dfs(root)
     return arr[ret] || null 
};
Copy the code

Verify the binary search tree

Analysis of the

1. The characteristics of binary search tree: the root node is larger than the left node and smaller than the right node
2. In the process of preorder traversal, it is the process of single increase;
3. We don’t need to maintain an array, we just need to maintain the last value and make size decisions
4. So in the preorder traversal process, and then a global traversal size can be compared;

 var isValidBST = function(root) {
    if(! root)return false
    let pre = -Infinity / / the minimum
    let ret = true // The default is
    const inorder  = (root) = > {
     
        if(root.left && ret) inorder(root.left)
           if(root.val<=pre) {
            ret = false // If there is a set of failures, it is not BST
            return
        }else {
            pre = root.val
        }
        if(root.right && ret) inorder(root.right)
    }
    inorder(root)
    return ret
};
Copy the code

Restore binary search tree

Analysis of the

1. Since the prompt is easy to implement with O(N){O(N)}O(N) space complexity, it is easier to get the result by simply storing the array in order to iterate, so let’s use the brute force solution
2. We get an array of nodes through the sequence first
3. The value of this array is definitely not single increment, so there are two values that are not the same as the value of the sorted array, so open another array and store the value, sort it, compare it, and change the corresponding value of the node
4. Time complexity O (nlogn) {O (nlogn)} O (nlogn), space complexity O (N) (N)} {O O (N)

${O(N)}$
var recoverTree = function(root) {
    const ret = []
    const dfs = (root) = > {
        if(! root)return
        dfs(root.left)
        ret.push(root)
        dfs(root.right)
    }
    dfs(root);

    // Move two values to increment the ret array
    // Open another array ret2 and sort
    let sorted = ret.map(item= > item.val)
    sorted.sort((a,b) = > a-b)
    sorted.forEach((sorted,index) = > {
        if(sorted ! == ret[index].val) { ret[index].val = sorted } }) };Copy the code

222. Number of nodes in a complete binary tree

You can get the number of nodes by simply traversing them once

var countNodes = function(root) {
    let ret = 0
    const preorder =  root= > {
        if(! root)return 
        ret++
        preorder(root.left)
        preorder(root.right)
    }
    preorder(root)
    return ret
};
Copy the code

Interview question 04.12. Sum up paths

Analysis — Dual DFS

1. The starting point is not limited, but the path must be down, so you can’t go backwards
2. Two DFS, one pointing to the start node and one looking down from the start node
3. Note 1: The values here are arbitrary, so you can’t use an out-of-value or a path to continue DFS, but you must scan the leaves
4. Time complexity O(NlogN){O(NlogN)}O(NlogN) is equivalent to each node in the tree being the initial node, and then traversing the subtree (find).

var pathSum = function (root, sum) {
  let ret = 0;

  // Traverse the DFS of the node
  const dfs = (root) = > {
    if(! root)return;
    find(root, 0);
    dfs(root.left);
    dfs(root.right);
  };

  const find = (root, total) = > {
    total += root;
    // if (total > sum) return; // Finish the jumper -- here
    if (total === sum) {
      // Meet the requirements
      ret++;
      // return;
    }
    if (root.left) find(root.left, total);
    if (root.right) find(root.right, total);
  };

  dfs(root);
  return ret;
};

Copy the code

Find the sum of the numbers from the root node to the leaf node

Analysis:

1. What we’re really looking at here is going from the root node to the leaf node as required, and the sum of the numbers is just a formality
2. Obviously, using preorder traversal, each time processing the value of the root node, and then processing the value of the left and right nodes, is consistent with the problem
3. Time complexity O(N){O(N)}O(N)

var sumNumbers = function (root) {
    let ret = 0
    const dfs = (root,num) = > {
        let cur = num*10+root.val
        if(! root.left && ! root.right) {// Leaves -- if you want to find a leaf node, you don't want to find a null under the leaf node
            ret+=cur
        }
        if(root.left) dfs(root.left,cur)
        if(root.right) dfs(root.right,cur)
    }

    dfs(root,0)
    return ret
}
Copy the code

Count the number of good nodes in the binary tree

Analysis of the

1. If the maximum value in the entire path is less than or equal to the value of the current node, then this node is node no
2. Only if it is a good node, you need to replace the maximum, and then you can find all the nodes
3. Time complexity O(N){O(N)}O(N)

var goodNodes = function(root) {
    let ret = 0

    const dfs = (root,max) = > {
        if(root.val>=max) {
            ret++
            max = ret
        }
        if(root.left) dfs(root.left,max)
        if(root.right) dfs(root.right,max)
    }

    dfs(root,-Infinity)
    return ret
};
Copy the code

Binary tree pruning

Analysis of the

1. We’re subtracting all the subtrees that don’t contain 1, so we can recursively drop all the subtrees that don’t meet the criteria from the bottom up
2. Bottom up is usually called recursion, search (recursion) until the null under the leaf node, and then start (recursion) to return the value, usually the final return value is directly rather than the outer global variable
3. For each root node, we are using a recursive function to the left and right subtrees of after pruning, and spell on the current node, if left subtree has been cut off (null), at the same time, their value is 0, then the subtree can cut off, the manifestation is returns null, then it’s on a layer of the parent node can identify this lesson subtree didn’t, Go all the way to the root node and return the final result
4. Time complexity: O(N){O(N)}O(N)

var pruneTree = function (root) {
  const recursion = (root) = > {
    if(! root)return null; // Null under the leaf node
    // Find the left and right trees
    root.left = recursion(root.left);
    root.right = recursion(root.right);
    if(! root.left && ! root.right && root.val ===0) return null; Subtree subtree subtree subtree subtree subtree subtree subtree subtree subtree subtree subtree subtree subtree subtree subtree subtree subtree subtree
    return root; // We can still salvage it
  };
  return recursion(root);
};
Copy the code

Remove the leaf node for the given value

Analysis of the

1. There are two criteria for deletion: leaf node + target
2. Once a leaf node is removed, its parent is likely to beAfter YangThen you need to continue deleting
3. So for bottom-up deletion, using post-order traversal is most appropriate.
4. Pruning is basically the same as pruning for a binary tree. Target is given in this case and 0 is given in this case
5. Time complexity: O(N){O(N)}O(N)

var removeLeafNodes = function (root, target) {
  const postOrder = (root) = > {
    if(! root)return null;
    root.left = postOrder(root.left);
    root.right = postOrder(root.right);
    // leaves a node and its value is equal to target
    if(! root.left && ! root.right && root.val === target)return null;
    return root;
  };
  return postOrder(root);
};
Copy the code

The maximum difference between a node and its ancestor

Analysis of the

1. With a top-down search, the maximum and minimum values of the current route are carried during the search, and the maximum difference can then be matched
2. The thing to notice is that the difference is at least two nodes, and that’s already qualified, so you don’t have to do that in the function, but you have to be careful when you initialize it
3. Here, the initial min and Max values of the path are directly taken from the root node, and then the search starts from the children of the root node, so there are left and right nodes, and the final result is returned
4. Time complexity: O(N){O(N)}O(N)

var maxAncestorDiff = function (root) {
  let ret = 0;

  const dfs = (root, min, max) = > {
    if(! root)return;
    ret = Math.max(ret, Math.abs(max - root.val), Math.abs(root.val - min));
    min = Math.min(min, root.val);
    max = Math.max(max, root.val);
    dfs(root.left, min, max);
    dfs(root.right, min, max);
  };
  // The problem is given at least two nodes
  // The root node is initialized as the maximum and minimum value of the initial path
  dfs(root.left, root.val, root.val);
  dfs(root.right, root.val, root.val);
  return ret;
};
Copy the code

865. The smallest tree with all deepest nodes

Analyze 1 — Find depth and match

1. Since the maximum depth is required, the maximum depth Max should be calculated from the top down, and then the maximum depth of the root node should be returned from the bottom up to find the matching maximum depth corresponding to the minimum node tree. When matching, you need to find the maximum depth first, and then match one to one;
2. Since we require the smallest subtree, but this subtree should contain all the nodes with maximum depth, we recursively return the maximum depth of the current node point tree. Only when there are nodes with maximum depth in the left and right subtrees of the subtree, we will replace the tree with a higher height, that is, a larger tree
3. The time complexity of recursively returning to the root node is O(N){O(N)}O(N).

var subtreeWithAllDeepest = function (root) {
  let max = 0; // The maximum depth
  let ret = undefined; // The target node
  const dfs = (root, depth) = > {
    // Leaf node -- preorder traversal to find the maximum depth
    if(! root) { max =Math.max(max, depth); // Find the maximum depth
      return depth;
    }
    const left = dfs(root.left, depth + 1);
    const right = dfs(root.right, depth + 1);

    // If the maximum depth of the left and right subtrees satisfies Max at the same time, then determine whether to replace with a larger subtree
    if (left === max && right === max) {
      // The nodes need to be replaced only when the maximum depth of the two subtrees is equal to the maximum depth
      ret = root;
    }
    // The root node is reached
    return Math.max(left, right); // Returns the maximum depth in the current node tree
  };
  dfs(root, 0);
  return ret;
};
Copy the code

Analysis 2 — The depth is not found

1. Before, we used global variables to hold the maximum depth and the minimum tree, and in fact every time we recurse, we can get left and right subtrees, including subtreesMaximum depthAs well asCorresponds to the smallest tree.
2. So recursion returnMaximum depthAs well asCorresponds to the smallest tree, you don’t need any extra variables
3. In fact, we don’t need to know what the maximum depth is, we just need to compare the depths and get the maximum one

var subtreeWithAllDeepest = function (root) {
  const dfs = (root, depth) = > {
    if(! root)return [root, depth];
    const [lr, ld] = dfs(root.left, depth + 1); // lr -- left root, ld -- left depth
    const [rr, rd] = dfs(root.right, depth + 1);
    if (ld === rd) return [root, ld]; // If the maximum value of the left and right trees is the same, the maximum depth nodes are on both sides, so update the minimum tree nodes
    if (ld > rd) return [lr, ld];
    if (ld < rd) return [rr, rd];
  };
  return dfs(root, 0);
};
Copy the code

Number of good leaf node pairs

Analysis of the

1. Look at the problem to find all the good leaf node pairs, since it is between leaf nodes, from the bottom up to find the distance between the two, it feels more intuitive
2. The second order iterates to the leaf nodes and starts to return. Since a node may have more than one leaf tree, it is stored as an array
3. If you recursively return an array of leaf nodes, you have to update the array of distances from the nodes to the leaf nodes
4. Then find out the nodes that meet the requirements in the distance between the left and right nodes, and finally combine all the leaf nodes to return
5. Time O(N){O(N)}O(N), space O(N){O(N)}O(N)

var countPairs = function (root, distance) {
  const ret = 0;
  const dfs = (root) = > {
    if(! root)return [];
    if(! root.left && ! root.right)return [0]; // Leaf node
    // Find the distance from the leaf node to the current node
    const left = dfs(root.left).map((i) = > i + 1);
    const right = dfs(root.right).map((i) = > i + 1);
    // Then find all node pairs less than dis
    for (let l of left) {
      for (let r of right) {
        if(l + r <= distance) ret++; }}// Close the leaves and return
    return [...left, ...right];
  };
  dfs(root);
  return ret;
};
Copy the code

894. All possible full binary trees

Analysis of the

1. If n is an even number, then return an empty array because it does not form a full binary tree. If there are only 1 nodes, then return [node] — this is the boundary
2. For each subtree, you’re buildingFull binary treeIn other words, for each child node, a full binary tree is built once until the boundary is known
3. Each layer is traversed to allocate the number of nodes in the left and right trees, and then usesSubsequent traversalTo the boundary condition, and then began to process;
4. Only when there are nodes in both left and right node trees, it is necessary to concatenate and combine into a new node array to recurse upward
5. The whole thing is to find a full binary tree by allocating the number of subtree nodes from the top down; Then the node tree is updated from bottom to top, and finally a compliant full binary tree node array is obtained.
6. Time complexity N2{N^2}N2, each layer needs to traverse the cut, after the cut is finished, the tree is created separately

var allPossibleFBT = function (n) {
  const recursion = (n) = > {
    if (n % 2= = =0) return []; / / even
    if (n === 1) return [new TreeNode(0)];
    const ret = []; // Save all nodes that meet the 'full binary tree' condition under the current node
    for (let i = 0; i < n; i++) {
      const left_num = i,
        right_num = n - i - 1; // The reason why we subtract one more is because the root node occupies one
      // Build a full binary tree of the left tree
      const lefts = recursion(left_num);
      const rights = recursion(right_num);
      if (lefts && rights) {
        // It is full only when it must exist simultaneously; Or none at all
        for (let l of lefts) {
          for (let r of rights) {
            const root = new TreeNode(0); root.left = l; root.right = r; ret.push(root); }}}}return ret;
  };
  return recursion(n);
};
Copy the code

96. Different binary search trees

Analysis – Violent split

1. For each child node in the BST, the subtree they are in is also a BST, so we need to know how many different BST [1,n] can be broken down into a set of subtrees in n ways. For example, given n == 3, Then it can be divided into three subtree node assignments of [0,2],[1,1] and [2,0]
2. So we can keep splitting off the net, and the boundary condition is that if the number of nodes is one or zero, there’s only one case, and then we start returning
3. And the value that comes back is the value that we want.
4. Time complexity n2logn{n^2logn}n2logn

var numTrees = function (n) {
  const recursion = (n) = > {
    if (n === 0) return 1;
    if (n === 1) return 1;
    let temp = 0;
    for (let i = 1; i <= n; i++) {
      const l = i - 1,
        r = n - i;
      const left = recursion(l);
      const right = recursion(r);
      temp += left * right;
    }
    return temp;
  };

  return recursion(n);
};
Copy the code

Analysis – dp

1. Based on the above theory, it is found that the number of BST that can be formed is only related to the number of ordered arrays n, and we only end up with a total value rather than a set of trees in each case;
2. Therefore, in the process of disassembly, recursion operations will be repeated to return the corresponding values. These values can actually be stored and used directly, for example, fn(1) = 1. Fn (2) = 2, etc., which can be stored in a set and then returned directly when solving without recursion.
3. And then I came up with the idea of using dp, where DP [I] tells you how many different BST’s you can have in an ordered array with an I and a value
4. Boundary conditions: DP [0] = DP [1] = 1
5. State transition equation: Dp [I] = Sum(dp[k]*dp[i-k]) dp[I] = Sum(dp[k]*dp[i-k]) dp[I] = Sum(dp[k]*dp[i-k])
6. Time complexity O(NlogN){O(NlogN)}O(NlogN), space complexity N{N}N

var numTrees = function (n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      dp[i] += dp[j] * dp[i - j - 1]; }}return dp[n];
};
Copy the code

437. Total path III

Analysis of the

1. Key points, the path must be downward, that is, not repeat the previous;
2. Then the starting point doesn’t have to be the root node, so you need to have a DFS traversal of different starting points
3. The end point is not necessarily the leaf node, so the compliant path may be obtained in the middle. However, since the value can be positive or negative, we must go to the leaf node to ensure not to miss
4. The outer is responsible for the preorder traversal to get the actual node, and the inner is responsible for finding the path starting from a subtree node and finding the targetSum
5. Time complexity O(NlogN){O(NlogN)}O(NlogN)

var pathSum = function (root, targetSum) {
  let ret = 0;
  const inner = (root, sum) = > {
    const temp = sum + root.val;
    if (temp === targetSum) ret++;
    if (root.left) inner(root.left, temp);
    if (root.right) inner(root.right, temp);
  };

  const outer = (root) = > {
    if(! root)return;
    inner(root, 0);
    outer(root.left);
    outer(root.right);
  };
  outer(root);
  return ret;
};
Copy the code

Difficult question

Vertical order traversal of binary trees

Analysis of the

1. This question is mainly based on the picture, which has marked some vertical order coordinates, so consider traversing once, annotate the vertical order position attribute of nodes, and then put the same vertical order position in the same array.
2. It is worth noting that in the subtree of the binary tree alternating with each other, there will be multiple values in the same vertical order position in the same level, and this time the problem also tells us how to deal withValues are sorted from smallest to largest only when rows and columns are the same;
3. Therefore, we cannot directly store all values in the same vertical order in the global map. Instead, we need to have a variable tempMap in each layer to deal with the order of possible values in the same layer and column, and then merge them into the global map.
4. After you walk through the tree and get a map, the key is the vertical position, the value is the corresponding value, and the map is an array
5. Sort the key values and turn them into a compliant array
6. The space complexity O(N){O(N)}O(N), the time complexity O(N){O(N)}O(N) + O(MlogM){O(MlogM)}O(MlogM), where N is the node value of the tree and M is the vertical order position width

 var verticalTraversal = function (root) {
    const ret = []
    const queue = []
    const map = new Map(a);// Total stores different vertical order of the array
    queue.push([root,0]) // The first argument is the node, the second argument is the vertical order distance -- in this case, the root node is 0

    while(queue.length) {
        let len = queue .length
        const tempMap = new Map(a)// Temporary map for each layer
        while(len--){
            // Enter each layer of processing
            const [root,index] = queue.shift()
            if(root.left) queue.push([root.left,index-1])
            if(root.right) queue.push([root.right,index+1])
            // Process the location of the current node
            if(tempMap.has(index)){
                tempMap.set(index,tempMap.get(index).concat(root.val))
            }else{
                tempMap.set(index,[root.val])
            }
        }
        for(let [index,val] of tempMap.entries()){
            val.sort((a,b) = >a-b)
            if(map.has(index)){
                map.set(index,map.get(index).concat(val))
            }else{
                map.set(index,val)
            }
        }
    }
    // This is done
    return [...map.keys()].sort((a,b) = > a-b).map(key= > map.get(key))
}
Copy the code

37. Serialize the binary tree

• This is just to give you a sense of why when we do tree problems, when we do tree problems (or linked lists), the console examples are arrays, not a visual tree structure of data, which I had a hard time understanding until I learned about serialization and deserialization.
• Personal understanding this is to compatible with different language built-in data structures and make optimization strategy, JS, for example, there is no this kind of structure, tree tree, so we are doing the need to build a class, and then use our commonly used data structure spanning tree, and then carry out calculations, and the process, is actually deserialization of the tree. Arrays, strings, as basic data structures, are almost always built into common language, so they’re preferred over trees.

Analyze — serialize — convert nodes to strings

1. When we look at a deserialized array or string subjectively, we match it from top to bottom and left to right, so when we serialize it, we use BFS directly
2. Now, the thing to notice here is that we’re storing it as a single string, and we end up with an extra “,” that needs to be removed
3. The time and space complexity are: O(N){O(N)}O(N),

 var serialize = function (root) {
  if(! root)return "";
  let ret = "";
  const queue = [];
  queue.push(root);
  while (queue.length) {
    let len = queue.length;
    let isNull = true; // Make sure that this layer is null. If it is null, then it is finished
    let str = "";
    while (len--) {
      const root = queue.shift();
      if(! root) {// When you deserialize, you don't know where the node is, so you have to use null as a placeholder
        str += "null"+ ",";
      } else {
        isNull = false;
        str += root.val + ","; queue.push(root.left); queue.push(root.right); }}// The first layer of traversal is complete
    if (isNull) {
      // This layer is null, so it's over
      return ret.substr(0,ret.length-1);
    } else {
      ret += str; // Add the string}}};Copy the code

Analyze — deserialize — turn strings into nodes

1. Given an array, deserialize a lesson tree
2. The BFS tiling mode is used. Two nodes are removed from nodes each time. If there are values, they are saved in the queue.
3. Specifically, queue holds the valued nodes, and index gets the left and right children of the ejected node (left and right are stored in nodes).
4. The time and space complexity are: O(N){O(N)}O(N);

var deserialize = function (data) {
    if(! data)return null / / blank nodes
    const nodes = data.split(', ') // Cut into an array
    const root = new TreeNode(nodes[0]); / / the root node
    const queue = [] // Queue to store nodes at each layer;
    queue.push(root)

    let index = 0; // The index of the current node
    while(index < nodes.length - 2) {const root = queue.shift()
      const lv = nodes[index+1]
      const rv = nodes[index+2]
      if(lv! = ='null') {
        const lnode = new TreeNode(lv)
        root.left = lnode
        queue.push(lnode)
      }
      if(rv! = ='null') {
        const rnode = new TreeNode(rv)
        root.right = rnode
        queue.push(rnode)
      }
      index +=2
    }
   
    return root

};
Copy the code

124. Maximum sum of paths in a binary tree

Analysis of the

1. The sum of the maximum paths at the root of a node, and the sum of the maximum paths at the cut-off point of a node, are two different values
2. The former root node is a ring in the path, if l -> root -> r
3. The latter, as the largest single path sum of the subtree, is returned to the parent node for judgment, such as L (e) -> root
4. So the whole is a recursive process, but in the recursive process there are local optimal solution to save;
5. The maximum value of recursion each time is containingThe root nodeIf the maximum value of the left and right subtrees in one of the lessons is larger than this, then the current value will be replaced in the recursion, no additional processing is required
6. The time is O(N){O(N)}O(N), and the space is O(1){O(1)}O(1).

var maxPathSum = function(root) {
    let max = -Infinity
    const dfs = root= > {
        if(! root)return 0
        const l = dfs(root.left)
        const r = dfs(root.right)
        // Root. val does not need to be compared with 0, and must contain the root node, otherwise it cannot join
        // If the maximum value of the monad tree is larger, it will replace Max in the later DFS
        const tempMax = Math.max(l,0) +Math.max(r,0)+root.val
        max =Math.max(max,tempMax) 
        return Math.max(0,l,r)+root.val // The root node must exist, otherwise it cannot be connected
    }
    dfs(root)
    return max
};
Copy the code

834. Sum of distances in the tree

leetcode-cn.com/problems/su…

Analysis of the

1. NodeNum specifies the total number of nodes in the root tree, including all children and the current root node. NodeNum [root] = sum(noChild])+1
2. DistSum = sum(dist[child]+nodeNum[root]) — distSum[root] = sum(dist[child]+nodeNum[root])
3. DistSum (nosum [Child]) ¶ distSum (nosum [Child]) ¶ distSum (nosum [Child])*1
4. The distSum here is the sum of the subtree distances, and we need to recurse from top to bottom to find the true sum of the distances of all the nodes
5. It should be noted that this is just a simulated tree, and the array saved is actually all nodes near the node. The reason why we divide the parent node into the parent node is to ensure that the first node is the parent node and the last node is the child node in the process of traversing again. So this line has no actual pointing relationship

var sumOfDistancesInTree = function(n, edges) {
    const graph= new Array().fill(null).map(() = > []) // The subscript is the coordinate of the root node, and the value is the array of coordinates of the child nodes
    for(let [from,to] of edges){
        graph[from].push(to) 
        graph[to].push(from)}const distSum = new Array(n).fill(0) // 1. Stores the sum of the distances of the subtree nodes
    const nodeNum = new Array(n).fill(1) // Stores the total number of nodes in the subtree
    This command is used to obtain the distSum and nosum of each node from the bottom up
    const postOrder = (root,parent) = > {
        const childs = graph[root]
        for(let child of childs) {
            if(child === parent) continue // The parent node is the node that has just been passed
            postOrder(child,root)
            nodeNum[root] += nodeNum[child]
            distSum[root] += distSum[child]+nodeNum[child]
        }
    }

    DistSum = distSum = distSum = distSum = distSum = distSum
    const preOrder = (root,parent) = > {
        const childs = graph[root]
        for(let child of childs) {
            if(child === parent) continue // The parent node is the node that has just been passed
            distSum[child] = distSum[root] - nodeNum[child] + ( n- nodeNum[child])
            preOrder(child,root)
        }
    }
    postOrder(0, -1)
    preOrder(0, -1)
    return distSum

};
Copy the code