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 article has a word limit, so divided into two, this article for the next welcome to pay attention to the update after!

5. Classic topic: Binary tree operation

(1) Flip binary trees

Flip a binary tree. Example:

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

After flipping, each left and right children of the binary tree have been exchanged. All can be realized by recursion: traversing every node and swapping the left and right children of each node.

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @return {TreeNode}* /
var invertTree = function(root) {
   if(! root){return root
   }
   // Recursively retrieve the left and right children
   let right = invertTree(root.right)
   let left = invertTree(root.left)
   // Swap the left and right children
   root.right = left
   root.left =right
   return root
};
Copy the code

Complexity analysis:

  • Time complexity: O(N), where N is the number of binary tree nodes. You have to go through every node in the binary tree, and for each node, you swap its two subtrees in constant time.
  • Space complexity: O(N). The space used is determined by the depth of the recursion stack, which is equal to the height of the current node in the binary tree. In the average case, the height of a binary tree is logarithmically related to the number of nodes, that is, O(logN). In the worst case, the tree forms a chain, and the space complexity is O(N).

(2) Merge binary trees

Given two binary trees, imagine that when you overlay one on top of the other, some of the nodes of the two binary trees overlap. You need to merge them into a new binary tree. The rule for merging is that if two nodes overlap, then their values are added as the new value after the node merge, otherwise the node that is not NULL is directly treated as the node of the new binary tree. Example 1:

Input: Tree1                     Tree 2                  
          1                         2/ \ \3   2                     1   3                        
       /                           \   \                      
      5                             4   7Output: Merged tree:3
	    / \
	   4   5
	  / \   \ 
	 5   4   7
Copy the code

Note: The merge must start at the root of both trees.

You can do it recursively, keep T1 awkward, just add t2 nodes to T1.

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} t1
 * @param {TreeNode} t2
 * @return {TreeNode}* /
var mergeTrees = function(t1, t2) {
    if(! t1 && t2){return t2
    }
    if(t1 && ! t2 || ! t1 && ! t2){return t1
    }

    t1.val += t2.val
    t1.left = mergeTrees(t1.left, t2.left)
    t1.right = mergeTrees(t1.right, t2.right)
    return t1
};
Copy the code

Complexity analysis:

  • Time complexity: O(min(m,n)), where m and n are the 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 explicitly merged, 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 the number of 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.

(3) The binary tree is expanded to a linked list

Given the root of the binary tree, you can expand it into a single linked list:

The expanded list should also use TreeNode, where the right pointer points to the next node in the list and the left pointer is always null. The expanded singly linked list should be traversed in the same order as the binary tree.

Example 1:

Enter: root = [1.2.5.3.4.null.6] Output: [1.null.2.null.3.null.4.null.5.null.6]
Copy the code

Example 2:

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

Example 3:

Enter: root = [0] Output: [0]
Copy the code

Tip:

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

Advanced: Can you use the in-situ algorithm (O(1) extra space) to expand the tree?

They also said that the expanded list is traversed in the same order as the binomial tree, so we can first traverse the binomial tree, and then put the result of the traversal into a linked list. This list is equivalent to a binary tree in which the left child nodes are null and the right child nodes are the values 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 {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    // Preorder traversal
    const fn = (root) = > {
        if(! root){return 
        }
        res.push(root)
        fn(root.left)
        fn(root.right)
    }

    let res = []
    fn(root)
    for(let i = 0; i < res.length - 1; i++){
        res[i].left = null
        res[i].right = res[i + 1]}};Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the number of nodes in the binary tree. The time complexity of preorder traversal is O(n). After preorder traversal, the information of left and right child nodes needs to be updated for each node, and the time complexity is also O(n).
  • Space complexity: O(n), where n is the number of nodes in the binary tree. The spatial complexity depends on the size of the stack (the recursion call stack or explicitly used in the iteration) and the list that stores the result of the preorder traversal. The number of elements in the stack does not exceed n, and the number of elements in the preorder traversal list is n.

(4) Construct binary trees for preorder and middle-order traversal sequences

The binary tree is constructed according to the fore-order traversal and in-order traversal of a tree. ** Note: ** You can assume that there are no duplicate elements in the tree. For example, give

Preorder = [3.9.20.15.7Inorder = [inorder = [9.3.15.20.7]
Copy the code

Returns the following binary tree:

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

Let’s look at the rules of preordered traversal and in-order traversal:

  • Preorder traversal: The root node + left subtree + right subtree preorder traversal
  • In order traversal: left subtree in order traversal + root node + right word word in order traversal

According to the above points, which is the left child node and which is the right child node, in order to judge.

The implementation steps are as follows:

  • Preorder traversal to find the root noderoot
  • findrootIn order traversal position -> left subtree length and right subtree length
  • Intercept the left subtree in order traversal, right subtree in order traversal
  • Truncate the preorder traversal of the left subtree and the right subtree
  • Reconstruct the binary tree recursively
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}* /
var buildTree = function(preorder, inorder) {
    if(! inorder.length)return null
    let tmp = preorder[0]
    let mid = inorder.indexOf(tmp)
    
    let root = new TreeNode(tmp)
    root.left = buildTree(preorder.slice(1,mid+1),inorder.slice(0,mid))
    root.right = buildTree(preorder.slice(mid+1),inorder.slice(mid + 1))
    return root
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the number of nodes in the tree.
  • Space complexity: O(n), in addition to the O(n) space required for the returned answer, the space of O(n) to store the hash map, and the space of O(h) (where H is the height of the tree) to represent the stack space for recursion. Here h is less than n, so the total space complexity is O(n).

(5) Construct binary trees from the middle order and post-order traversal sequences

Binary tree is constructed according to the middle order traversal and the post order traversal of a tree. Note: You can assume that there are no duplicate elements in the tree. For example, give

Inorder = [inorder = [9.3.15.20.7Postorder = [9.15.7.20.3]
Copy the code

Returns the following binary tree:

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

Let’s look at the rule of sequential traversal and post-sequential traversal in:

  • In order traversal: left subtree in order traversal + root node + right word word in order traversal
  • Post-order traversal: post-order traversal of left subtree + post-order traversal of right subtree + root node

The idea behind this topic is to use recursion:

  • As you can see, the last value of the sequential traversal set is the root node of the binary tree, which is 7 in our example
  • Based on the value of the root node, I find the index of that value in the array that I ordered in, and I know that to the left of 3 is the array that I ordered in the left subtree, and after 3 is the array that I ordered in the right subtree
  • Based on the value of the root node, the value of the index found in the subsequent traversal sets is the array of the left subtree, and the following values are the array of the right subtree, excluding the root node.
  • Recursion operation is performed according to the result of the sequence traversal and subsequent traversal of the left and right subtrees obtained above
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}* /
var buildTree = function(inorder, postorder) {
    if(! inorder.length)return null
    let len = postorder.length
    let tmp = postorder[len-1]
    let mid = inorder.indexOf(tmp)
    
    let root = new TreeNode(tmp)
    root.left = buildTree(inorder.slice(0,mid), postorder.slice(0,mid))
    root.right = buildTree(inorder.slice(mid + 1), postorder.slice(mid,len-1))
    return root
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the number of nodes in the tree.
  • Space complexity: O(n), in addition to the O(n) space required for the returned answer, the space of O(n) to store the hash map, and the space of O(h) (where H is the height of the tree) to represent the stack space for recursion. Here h is less than n, so the total space complexity is O(n).

(6) Construct binomial tree for preorder and postorder traversal sequences

Returns any binary tree that matches the given preorder and postorder traversal. Where the values in pre and POST traversals are different positive integers. Example:

Type: pre = [1.2.4.5.3.6.7], post = [4.5.2.6.7.3.1] Output: [1.2.3.4.5.6.7]
Copy the code

Tip:

  • 1 <= pre.length == post.length <= 30
  • Pre [] and post[] are both 1, 2… , pre-length
  • Each input is guaranteed to have at least one answer. If there are multiple answers, you can return one of them.

Let’s look at the rules of preordered and postordered traversal:

  • Preorder traversal: The root node + left subtree + right subtree preorder traversal
  • Post-order traversal: post-order traversal of left subtree + post-order traversal of right subtree + root node

The idea behind this topic is to use recursion:

  • According to the preorder traversal characteristics, we know that 1 is the root node of the binary tree, so the next node should be the left node, which is 2.
  • If we find the position corresponding to 2 in the post-order traversal, we can know that 2 and all the numbers before it are the post-order traversal group of the left node of the binary tree, and all the numbers after it are the post-order traversal group of the right node of the binary tree (with the root node removed).
  • Finds the preorder traversal values of the left and right subtrees in the preorder traversal based on the length of the left subtree.
  • We recurse to get the final binary tree.
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {number[]} pre
 * @param {number[]} post
 * @return {TreeNode}* /
var constructFromPrePost = function(pre, post) {
    if(! pre.length)return null
    let tmp = pre[0];
    let index = post.indexOf(pre[1]);
    let root = new TreeNode(tmp);
    
    root.left = constructFromPrePost(pre.slice(1,index+2),post.slice(0,index+1));
    root.right = constructFromPrePost(pre.slice(index+2),post.slice(index+1,post.length-1));
    return root;
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the number of nodes in the tree.
  • Space complexity: O(n), in addition to the O(n) space required for the returned answer, the space of O(n) to store the hash map, and the space of O(h) (where H is the height of the tree) to represent the stack space for recursion. Here h is less than n, so the total space complexity is O(n).

(7) Fill the next right node pointer of each node

Given a perfect binary tree, all the leaf nodes are at the same level, and each parent node has two children. A binary tree is defined as follows:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
Copy the code

Fill in each of its next Pointers so that the pointer points to its next right node. If the next right node cannot be found, the next pointer is set to NULL. Initially, all next Pointers are set to NULL.

Example:

Input: {"$id":"1"."left": {"$id":"2"."left": {"$id":"3"."left":null."next":null."right":null."val":4},"next":null."right": {"$id":"4"."left":null."next":null."right":null."val":5},"val":2},"next":null."right": {"$id":"5"."left": {"$id":"6"."left":null."next":null."right":null."val":6},"next":null."right": {"$id":"Seven"."left":null."next":null."right":null."val":7},"val":3},"val":1} output: {"$id":"1"."left": {"$id":"2"."left": {"$id":"3"."left":null."next": {"$id":"4"."left":null."next": {"$id":"5"."left":null."next": {"$id":"6"."left":null."next":null."right":null."val":7},"right":null."val":6},"right":null."val":5},"right":null."val":4},"next": {"$id":"Seven"."left": {"$ref":"5"},"next":null."right": {"$ref":"6"},"val":3},"right": {"$ref":"4"},"val":2},"next":null."right": {"$ref":"Seven"},"val":1}
Copy the code

Explanation: Given A binary tree as shown in Figure A, your function should fill each of its next Pointers to point to its next right node, as shown in Figure B.

Tip:

  • You can only use constant level extra space.
  • Recursion also works, where the stack space taken up by the recursion program does not count as additional space complexity

Here we use a recursive approach to solve the problem. We do a preorder traversal of the binary tree. We will discuss two cases: the left and right nodes of the same parent are connected, and the left and right nodes of a different parent are connected, as follows:

  • The first step is to connect the left and right nodes of the same parent node and point the value of the left node to the right node
  • In the second part, for the left and right nodes that are not the same parent node, take 5 and 6 in the figure as an example, we find the right node 3 through the parent node 2 of 5, and then find its left node through 3, and connect 5 with 3.

For the above steps, recurse until all nodes are traversed.

/** * // Definition for a Node. * function Node(val, left, right, next) { * this.val = val === undefined ? null : val; * this.left = left === undefined ? null : left; * this.right = right === undefined ? null : right; * this.next = next === undefined ? null : next; *}; * /

/ * * *@param {Node} root
 * @return {Node}* /
var connect = function(root) {
    if(! root)return null
	// The left and right nodes of the same parent are connected
    if(root.left && root.right){
        root.left.next = root.right
    }
	// Left and right nodes that are not the same parent are connected
    if(root.right && root.next && root.next.left){
        root.right.next = root.next.left
    }
	// Iterate recursively
    connect(root.left)
    connect(root.right)
    return root
};
Copy the code

Complexity analysis:

  • Time complexity: O(N), where N is the number of nodes in the binary tree, each node is accessed only once.

  • Space complexity: O(1), no need to store additional nodes.

(8) Fill the next right node pointer II of each node

Given a binary tree:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
Copy the code

Fill in each of its next Pointers so that the pointer points to its next right node. If the next right node cannot be found, the next pointer is set to NULL. Initially, all next Pointers are set to NULL.

Advanced:

  • You can only use constant level extra space.
  • Recursion also works, where the stack space taken up by the recursion program does not count as additional space complexity.

Example:

Input: root = [1,2,3,4,5,null,7] output: [1,#,2,3,#,4,5,7,#] explanation: given A binary tree as shown in figure A, your function should fill each of its next Pointers to point to its next right node, as shown in figure B. The serialized output goes through the sequence of layers (connected by the next pointer), with the ‘#’ indicating the end of each layer.

Tip:

  • The number of nodes in the tree is less than6000
  • -100 <= node.val <= 100

For this problem, we can sequence through the tree, the tree is based on breadth first traversal, in order to walk the layer, we need to use a queue, the queue that holds the nodes of the current layer.

When the queue is not empty, the current queue length len is recorded, and when traversing the layer, the next pointer of the node in this layer is changed, so that each layer can be organized into a linked list.

/** * // Definition for a Node. * function Node(val, left, right, next) { * this.val = val === undefined ? null : val; * this.left = left === undefined ? null : left; * this.right = right === undefined ? null : right; * this.next = next === undefined ? null : next; *}; * /

/ * * *@param {Node} root
 * @return {Node}* /
var connect = function(root) {
    if(! root) {return null;
    }
    const queue = [root];
    while (queue.length) {
        const len = queue.length;
        let last = null;
        for (let i = 1; i <= len; ++i) {
            let node = queue.shift();
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
            if(i ! = =1) { last.next = node; } last = node; }}return root;
};
Copy the code

Complexity analysis:

  • Time complexity: O(N). Where N is the number of nodes in the tree, we need to traverse all the points in the tree, and the time complexity is O(N).
  • Space complexity: O(N). Where N is the number of nodes in the tree, we need to initialize a queue whose length does not exceed the maximum number of nodes in the tree.

(9) Binary tree serialization and deserialization

Serialization is the operation of converting a data structure or object into continuous bits. The converted data can be stored in a file or memory, or transferred to another computer environment over the network, and the original data can be reconstructed in the reverse way.

Please design an algorithm to realize the binary tree serialization and deserialization. There is no restriction on your sequence/deserialization algorithm to perform logic, you just need to ensure that a binary tree can be serialized to a string and deserialize the string to the original tree structure.

Example: You can place the following binary tree:

    1
   / \
  2   3
     / \
    4   5Serialized as"[1, 2, 3, null, null, 4, 5)"
Copy the code

Tip: This is consistent with the way LeetCode is currently used, see LeetCode serialized binary tree format for details. You don’t have to take this approach, you can take other approaches to the problem.

Note: Do not use class member/global/static variables to store state. Your serialization and deserialization algorithms should be stateless.

For this binary tree problem, the most direct approach we can think of is the depth-first Bentley and breadth-first traversal, and here we solve it in two different ways.

Depth first traversal:

  • The first is a serialized binary tree. You can define a traversal method that accesses the root node, then the left node, and finally the right node, storing the value of each node in an array, and if it is null, storing it in an array.
  • The next step is to deserialize the binary tree, which is to convert the array into a binary tree, because the array is the result of the first order traversal of the binary tree, so we can traverse the array and restore the binary tree in the order of the root node, the left subtree, and the right subtree

Breadth first traversal:

  • The first is a serialized binary tree. Breadth first traversal is done from the top down (sequential traversal), so we can take advantage of the first-in, first-out (FIFO) nature of queues to maintain an array. First, queue the root node, then queue the left node and the right node, recursively.
  • Then we deserialize the binary tree. We can take the first element from the array to generate the root node, add the root node to the queue, circulate the queue, add the left and right subtrees of the root node to the queue respectively, and circulate this operation until the queue is empty. Nodes in the queue are used to traverse their left and right children later.

1) Depth-first traversal:

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}* /
var serialize = function(root) {
    const result = []
    function traverseNode(node){
        if(node === null){
            result.push(null)}else{
            result.push(node.val)
            traverseNode(node.left)
            traverseNode(node.right)
        }
    }
    traverseNode(root)
    return result
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}* /
var deserialize = function(data) {
    const len = data.length
    if(! len){return null
    }
    let i = 0
    function structure (){
        // Recursive stop condition
        if(i >= len){
            return null
        }
        const val = data[i]
        i++
        if(val === null) {return null
        }
        const node = new TreeNode(val)
        node.left = structure()
        node.right = structure()
        return node
    }
    return structure()
};

/** * Your functions will be called as such: * deserialize(serialize(root)); * /
Copy the code

Complexity analysis:

  • Time complexity: In the serialization and deserialization functions, we only access each node once, so the time complexity is O(n), where n is the number of nodes, that is, the size of the tree.
  • Space complexity: In serialization and deserialization functions, we recursively use stack space, so the progressive space complexity is O(n).

2) Breadth first traversal:

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}* /
var serialize = function(root) {
    if(! root){return[]}const result = []
    const queue = []
    queue.push(root)

    let node ;
    while(queue.length){
        node = queue.shift()
        result.push(node ? node.val : null)
        if(node){
            queue.push(node.left)
            queue.push(node.right)
        }
    }
    return result
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}* /
var deserialize = function(data) {
    const len = data.length
    if(! len){return null
    }
    const root = new TreeNode(data.shift())
    const queue = [root]
    while(queue.length){
        // Fetch the node to be traversed
        const node = queue.shift()
        if(! data.length){break
        }
        Restore the left node
        const leftVal = data.shift()
        if(leftVal === null){
            node.left = null
        }else{
            node.left = new TreeNode(leftVal)
            queue.push(node.left)
        }
        if(! data.length){break
        }

        // Restore the right node
        const rightVal = data.shift()
        if(rightVal === null){
            node.right = null
        }else{
            node.right = new TreeNode(rightVal)
            queue.push(node.right)
        }
    }
    return root
};

/** * Your functions will be called as such: * deserialize(serialize(root)); * /
Copy the code

Complexity analysis:

  • Time complexity: In the serialization and deserialization functions, we only access each node once, so the time complexity is O(n), where n is the number of nodes, that is, the size of the tree.
  • Space complexity: In serialization and deserialization functions, we recursively use stack space, so the progressive space complexity is O(n).

6. Classic topic: Properties of binary search trees

(1) Verify binary search tree

Given a binary tree, judge whether it is a valid binary search tree. Suppose a binary search tree has the following characteristics:

  • The left subtree of a node contains only the number smaller than the current node.
  • The right subtree of a node contains only the number greater than the current node.
  • All left and right subtrees must themselves also be binary search trees.

Example 1:

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

Example 2:

Input:5
   / \
  1   4
     / \
    3   6Output:falseExplanation: The input is: [5.1.4.null.null.3.6]. The value of the root is5, but its right child node has a value of4 。
Copy the code

First, DFS (depth-first traversal) is used to recursively traverse the entire tree, checking whether the relationship left < root < right is satisfied in each subtree.

Set two values: the maximum value and the minimum value are positive infinity and negative infinity respectively, and then judge whether the binary tree is a binary search tree by judging whether the value of the left child is less than the root node, and whether the value of the right child is greater than the root node.

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @return {boolean}* /
var isValidBST = function(root) {
   function dfs(root, minValue, maxValue){
       // Determine if the tree is empty
       if(! root){return true
       }
       // The key judgment condition: left < root < right
       if(root.val <= minValue || root.val >= maxValue){
           return false
       }
       // Traverse the left and right subtrees
       return dfs(root.left, minValue, root.val)&&dfs(root.right, root.val, maxValue)
   }
   // Initialize the DFS traversal
   return dfs(root, -Infinity.Infinity)};Copy the code

Complexity analysis:

  • Time complexity: O(n) : Each node of the binary tree can be accessed at most once during the recursive invocation, so the time complexity is O(n).
  • Space complexity: O(n) : recursive functions need to allocate stack space for each layer of recursive functions during recursion, so extra space is needed here and the space depends on the depth of recursion, i.e. the height of the binary tree. In the worst case, the binary tree is a chain, the height of the tree is NN, and the deepest recursive level is NN, so the space complexity in the worst case is O(n).

【 Method 2 】 in order traversal using binary tree in order traversal history judgment. We know: the binary search tree in order traversal is ordered. So, I’m just going to go through the binary tree, and I’m going to go through the array, and I’m going to see if it’s ordered.

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @return {boolean}* /
var isValidBST = function(root) {
   const queue = []
   function dfs(root){
       if(! root){return true
       }
       if(root.left){
           dfs(root.left)
       }
       if(root){
           queue.push(root.val)
       }
       if(root.right){
           dfs(root.right)
       }
   }
   dfs(root)
   // Check whether the result of the traversal is ordered
   for(let i = 0; i<queue.length-1; i++){
       if(queue[i] >= queue[i+1]) {return false}}return true
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the number of nodes in the binary tree. Each node of a binary tree is accessed at most once, so the time complexity is O(n).
  • Space complexity: O(n), where n is the number of nodes in the binary tree. The stack stores a maximum of N nodes, so additional O(n) of space is required.

(2) The KTH smallest element in the binary search tree

Given a binary search tree, write a function kthSmallest to find the kthSmallest element in it. Note: You can assume that k is always valid and that 1 ≤ k ≤ number of binary search tree elements.

Example 1:

Enter: root = [3.1.4.null.2], k = 1
   3
  / \
 1   4
  \
   2Output:1
Copy the code

Example 2:

Enter: root = [5.3.6.2.4.null.null.1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1Output:3
Copy the code

Advanced: if the binary search tree is often modified (insert/delete operations) and you need to find the kthSmallest value frequently, how can you optimize the kthSmallest function?

We know that the left node of a binary search tree is less than its parent, and the right node is less than its right node. In this way, the ordered traversal of the binary search tree is an ordered sequence from small to large. And we can do it in terms of this property.

Recursion: the binary search tree in order traversal, traversal principle is first traversed the left subtree, then traversed the root node, and finally traversed the left subtree. In the process of traversal, the result of traversal is continuously stored in the array, and when traversal reaches the KTH element, the traversal terminates.

Iteration: The recursive method also uses the binary search tree in the order of traversal:

  1. Initializes a node in the stack staging tree
  2. First, the root node is traversed, then the left subtree is traversed, and stored in the stack
  3. After traversing the left subtree, the elements in the stack will be out of the stack, so the order is reversed, become the root node traversed first, then traversed the left subtree
  4. And as we go through it, every time we go through it, k goes down by one
  5. And then you go through the left subtree and then you go through the right subtree
  6. Loop until k is zero, returning the current node value.
/** * 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
 * @param {number} k
 * @return {number}* /

// Recursive implementation:
var kthSmallest = function(root, k) {
    const result = []
    function travel(node){
        if(result.length >= k) return 
        if(node.left){
            travel(node.left)
        }
        result.push(node.val)
        if(node.right){
            travel(node.right)
        }
    }
    travel(root)
    return result[k - 1]};// Iteration implementation:
let kthSmallest = function(root, k) {
    let stack = []
    let node = root
   
    while(node || stack.length) {
        // Traverse the left subtree
        while(node) {
            stack.push(node)
            node = node.left
        }
     
        node = stack.pop()
        if(--k === 0) {
            return node.val
        }
        node = node.right
    }
    return null
}
Copy the code

Complexity analysis of recursion:

  • Time complexity: O(n), where n is the number of nodes in the binary tree, and the entire tree needs to be traversed.
  • Space complexity: O(n), using an array of stored sequences.

Complexity analysis of iteration:

  • Time complexity: O(H+k), where H refers to the height of the tree, since the tree must first descend to the leaves before starting the traversal, when the tree is a balanced tree: the complexity is O(logN+k). When the tree is an unbalanced tree: the complexity is O(N+k), and all nodes are in the left subtree.
  • Space complexity: O(H+k). When the tree is a balanced tree: O(logN+k). When the tree is an unbalanced tree: O(N+k).

(3) The KTH largest node of the binary search tree

Given a binary search tree, find the KTH largest node in it.

Example 1:

Enter: root = [3.1.4.null.2], k = 1
   3
  / \
 1   4
  \
   2Output:4
Copy the code

Example 2:

Enter: root = [5.3.6.2.4.null.null.1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1Output:4
Copy the code

Limitation: 1 ≤ K ≤ Number of binary search tree elements

We know that the result of a binary search tree is an array of large and small objects, so we can go backwards and return the KTH largest node of the result.

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

    const dfs = (root) = > {
        if(! root){return 
        }

        dfs(root.right)
        res.push(root.val)
        dfs(root.left)
    }
    dfs(root)

    return res[k - 1]};Copy the code

Complexity analysis:

  • The time complexity is O(n). In the worst case, when the tree is reduced to a linked list (all right child nodes), the recursion depth is n regardless of the value of k and takes O(n) time;
  • Space complexity O(n). In the worst case, when the tree is reduced to a linked list (all right child nodes), the system uses O(n) size stack space.

(4) Minimum absolute difference of binary search tree

Given a binary search tree where all nodes are non-negative, calculate the minimum absolute value of the difference between any two nodes in the tree. Example:

Input:1
    \
     3
    /
   2Output:1Explanation: The minimum absolute difference is1, including2 和 1The absolute value of the difference between PI and PI is PI1(or2 和 3).Copy the code

Tip: There are at least two nodes in the tree.

The value of the left subtree is always less than the value of the parent node, and the value of the right subtree is always greater than the parent node. It is also important to note that in the binary search tree traversal, the result of the in-order traversal is an ascending array.

Then we can do an in-order traversal and compare the values of the neighboring nodes, always keeping the result to the lowest value currently available.

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @return {number}* /
var getMinimumDifference = function(root) {
    let pre = null
    let min = Infinity
    
    let inOrderTravel = (root) = > {
        if(root){
            inOrderTravel(root.left)
            if(pre){
                min = Math.abs(root.val - pre.val) < min ? Math.abs(root.val - pre.val) : min
            }
            pre = root
            inOrderTravel(root.right)
        }
    }
    inOrderTravel(root)
    return min
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the number of nodes in the binary search tree. Each node is accessed once and only once in the in-order traversal, so the total time complexity is O(n).
  • Space complexity: O(n). The spatial complexity of the recursive function depends on the stack depth of the recursion, which is O(n) in the case of a binary search tree as a chain.

(5) mode in binary search tree

Given a binary search tree (BST) with the same value, find all modes (the most frequently occurring elements) in the BST. Suppose BST has the following definition:

  • The value of nodes in the left subtree of nodes is less than or equal to the value of the current node
  • The value of the node in the right subtree of the node is greater than or equal to the value of the current node
  • Both the left and right subtrees are binary search trees

Example: given BST [1,null,2,2],

   1
    \
     2
    /
   2Return to the [2].
Copy the code

Tip: If the mode is more than 1, do not consider the output order progression: can you use no extra space? (Assuming the overhead of the implicit call stack generated by recursion is not counted)

For this problem, we can undertake depth-first traversal of binary tree, in the process of traversal, initialize a Max, used to hold the largest number of the current element, the binary tree values with the corresponding number stored in a map, finally we traverse over the map, put all the number equals the Max value is stored 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 findMode = function(root) {
    let map = {}, max = 0, res = []

    const dfs = (root) = > {
        if(! root){return []
        }
        map[root.val] ? map[root.val] += 1 : map[root.val] = 1;

        max = Math.max(max, map[root.val])
        dfs(root.left)
        dfs(root.right)
    }
    dfs(root)
    
    for(let key in map){
        if(max === map[key]){
            res.push(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.
  • 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.

7. Classic topic: Binary search tree operation

(1) Convert the ordered array into a binary search tree

Convert an ordered array in ascending order to a highly balanced binary search tree. In this case, a height-balanced binary tree means that the absolute value of the height difference between the left and right subtrees of a binary tree _ for each node _ is less than 1. Example: Given an ordered array: [-10,-3,0,5,9], one possible answer is: [0,-3,9,-10, NULL,5], which can represent the following highly balanced binary search tree:

      0
     / \
   -3   9
   /   /
 -10  5
Copy the code

Binary recursive implementation: the value of the array into a highly balanced binary search tree, as long as we find the middle element as the root node, and then the left and right of the middle element are divided, find the middle value as the root node of the subtree, repeat the operation, until traversing the entire array can be.

  • When the length of the array is odd, the intermediate value is taken as the root node, and the difference between the two sides of the balanced binary search tree is 0.
  • When the array length is even, you can take either of the middle two elements as the root node, so that the absolute value of the difference between the two sides of the balanced binary tree is 1.
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {number[]} nums
 * @return {TreeNode}* /
var sortedArrayToBST = function(nums) {
   if(! nums.length){return null
   }
   function bst(low, high){
       // Iterate over the end condition
       if(low > high){
           return null
       }
       // Retrieve the index value of the middle element of the current subsequence
       const mid = Math.floor(low+(high-low)/2)
       // Make the value of the intermediate element the root node of the current subtree
       const cur = new TreeNode(nums[mid])
       // Recursively build the left subtree
       cur.left = bst(low, mid-1)
       // Recursively construct the right subtree
       cur.right = bst(mid+1, high)
       return cur
   }
   return bst(0, nums.length-1)};Copy the code

Complexity analysis:

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

(2) Search in binary tree search tree

Given the root node of a binary search tree (BST) and a value. You need to find a node in the BST whose node value is equal to the given value. Returns a subtree with this node as the root. Returns NULL if the node does not exist. For example,

Given a binary search tree:4
   / \
  2   7
 / \
1   3And values:2
Copy the code

You should return as the subtree:

  2     
 / \   
1   3
Copy the code

In the example above, if the value we are looking for is 5, but there is no node with a value of 5, we should return NULL.

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

// Iteration implementation:
var searchBST = function(root, val) {
   while(root){
       if(root.val === val){
           return root
       }else if(root.val <val){
           root = root.right
       }else{
           root = root.left
       }
   }
   return null
};

// Recursive implementation:
var searchBST = function(root, val) {
   if(! root){return null
   }
   if(root.val === val){
       return root
   }else if(root.val < val){
       return searchBST(root.right, val)
   }else{
       return searchBST(root.left, val)
   }
};
Copy the code

Complexity analysis of iteration:

  • Time complexity: O(H), where H is tree height. The average time complexity is O(logN), and the worst time complexity is O(N).
  • Space complexity: O(1), constant extra space.

Complexity analysis of recursion:

  • Time complexity: O(H), where H is tree height. The average time complexity is O(logN), and the worst time complexity is O(N).
  • Space complexity: O(H), depth of recursion stack is H. The depth is O(logN) in the average case and O(N) in the worst case.

(3) Insert operation in binary search tree

Given the root node of a binary search tree (BST) and the value to be inserted into the tree, the value is inserted into the binary search tree. Returns the root node of the inserted binary search tree. Ensure that no new values exist in the original binary search tree. Note that there can be a number of valid inserts, as long as the tree remains a binary search tree after insertion. You can return any valid result.

For example,

Given a binary search tree:4
   / \
  2   7
 / \
1   3And the inserted values:5
Copy the code

You can return this binary search tree:

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

Or the tree is valid:

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

Properties of binary search trees: for any node root, all nodes on the left subtree (if there is one) have a value less than root.val, and all nodes on the right subtree (if there is one) have a value greater than root.val, and they are all binary search trees.

Therefore, when inserting val into a subtree with root as its root, the size relationship between val and root.val can determine which subtree to insert val into.

  • If the subtree is not empty, the problem becomes inserting val into the corresponding subtree.
  • Otherwise, create a new node here with the value val and link to its parent node root.
/** * 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
 * @param {number} val
 * @return {TreeNode}* /

// Recursive implementation:
var insertIntoBST = function(root, val) {
    if(! root){return  new TreeNode(val)
    }
    if(val < root.val){
        root.left = insertIntoBST(root.left,val)
    }else{
        root.right = insertIntoBST(root.right,val)
    }
    return root
};

// Iteration implementation:
var insertIntoBST = function(root, val) {
    if(! root){return new TreeNode(val)
    }
    let cur = root
    while(cur){
        if(val > cur.val){
           if(! cur.right){ cur.right =new TreeNode(val)
                return root
           }else{
               cur = cur.right
           }
        }else{
            if(! cur.left){ cur.left =new TreeNode(val)
                return root
            }else{
                cur = cur.left
            }
        }
    }
    return root
};
Copy the code

Complexity analysis of iteration:

  • Time complexity: O(N), where N is the number of nodes in the tree. In the worst case, you need to insert the value into the deepest leaf of the tree, which is O(N).
  • Space complexity: O(1). We’re only using constant size space.

Complexity analysis of recursion:

  • Time complexity: O(N), where N is the number of nodes in the tree. In the worst case, you need to insert the value into the deepest leaf of the tree, which is O(N).
  • Space complexity: O(1). We’re only using constant size space.

(4) Balance the binary search tree

Given a binary search tree, you are asked to return a balanced binary search tree with the same node values as the original tree. A binary search tree is said to be balanced if the height difference between the two subtrees of each node is less than one. If there are multiple constructors, return any one of them.

Example:

Enter: root = [1.null.2.null.3.null.4.null.null] Output: [2.1.3.null.null.null.4[Explanation: This is not the only correct answer, [3.1.4.null.2.null.null] is also a feasible construction scheme.Copy the code

Tip:

  • The number of tree nodes is between 1 and 10.
  • The value of the tree nodes varies from one to 10.

The idea is similar to the above problem of turning an ordered array into a highly balanced binary search tree.

We know that a binary search tree is an ordered array, so we can do an ordered walk of the binary search tree that they gave us, and turn that ordered array into a balanced binary search tree. The second half of the problem is exactly the same as before.

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @return {TreeNode}* /
var balanceBST = function(root) {
   // Initialize an array to store the results of an ordered traversal
   const nums = []
   // Perform in-order traversal of the binary search tree
   function inorder(root){
       if(! root){return 
       }
       inorder(root.left)
       nums.push(root.val)
       inorder(root.right)
   }
   // Convert the ordered array into a highly balanced binary search tree
   function buildAvl(low, high){
       if(low > high){
           return null
       }
       const mid = Math.floor(low+(high-low)/2)
       const cur = new TreeNode(nums[mid])
       cur.left = buildAvl(low, mid-1)
       cur.right = buildAvl(mid+1, high)
       return cur
   }
   inorder(root)
   return buildAvl(0, nums.length-1)};Copy the code

Complexity analysis:

  • Time complexity: Since each node can be accessed at most once, the total time complexity is O(N), where N is the length of the list.
  • Space complexity: Although recursion is used, the bottleneck is not stack space, but the nums array of length N, so the space complexity is O(N), where N is the total number of nodes in the tree.

(5) Convert the ordered list into a binary search tree

Given a single linked list whose elements are sorted in ascending order, convert it to a highly balanced binary search tree. In this case, a height-balanced binary tree is a binary tree where the absolute value of the height difference between the left and right subtrees of each node is less than 1. Example:

Given ordered list: [-10, -3.0.5.9], one possible answer is: [0, -3.9, -10.null.5], which can represent the following highly balanced binary search tree:0
     / \
   -3   9
   /   /
 -10  5
Copy the code

Since the array is ordered incrementing, we can start looking in the middle of the array. Recursion + dichotomy is used to solve this problem. The specific implementation ideas are as follows:

  • Find the middle element of the array as the value of the root node of the binary tree
  • The left node of the binary tree is0 - mid - 1The element corresponding to the intermediate coordinate of theta
  • The right node of the binary tree isMid + 1, arr. Length - 1The intermediate coordinate of theta corresponds to the element
  • Recursion continues as above until the array elements are traversed

It is important to note that the final result may not be unique.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/** * 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 {ListNode} head
 * @return {TreeNode}* /
var sortedListToBST = function(head) {
    const arr=[];
    while(head){
        arr.push(head.val)
        head = head.next
    }
    const resTree=function(left, right){
        if(left > right) return null
        const mid = Math.floor(left + (right - left)/2); 
        const res = new TreeNode(arr[mid]);
        res.left = resTree(left, mid-1);
        res.right = resTree(mid+1, right);
        return res
    }
    return resTree(0, arr.length-1)};Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the length of the array. Each number is accessed only once.
  • Space complexity: O(logn), where n is the length of the array. The spatial complexity does not take into account the return value, so the spatial complexity depends primarily on the depth of the recursion stack, which is O(logn).

(6) The binary search tree is converted to the accumulation tree

Given a Binary Search Tree, convert it to a Greater Tree, such that the value of each node is the sum of the original node’s value plus the values of all nodes Greater than it. Such as:

Enter: Original binary search tree:5
            /   \
           2     13Output: convert to an accumulation tree:18
            /   \
          20     13
Copy the code

Again, this is an easy problem, because we know that the result of an ordered walk through a binary tree is an increasing array. Here we can do an in-order traversal in reverse order, so that the array that comes out of it is decrement.

In order traversal order is ** left subtree → root node → right subtree. ** So you can first traverse the right subtree, then the root node, and finally traverse the left subtree.

In this case, if you set the value of a node that continues to accumulate, then the value at the current node will be assigned to the sum of larger numbers.

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

    const inOrder = (root) = > {
        if(! root){return 
        }
        if(root.right){
            inOrder(root.right)
        }
        sum += root.val
        root.val = sum
        if(root.left){
            inOrder(root.left)
        }
    }
    inOrder(root)
    return root
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the number of nodes in the binary search tree. Each node is traversed exactly once.
  • Space complexity: O(n), is the stack overhead in the recursion process, is O(logn) in the average case, and is O(n) in the worst case.

(7) Trim the binary search tree

I give you the root of the binary search tree, root, and I give you the minimum boundary, low, and the maximum boundary, high. The binary search tree is pruned so that all nodes have values in [low, high]. Pruning the tree should not change the relative structure of the elements that remain in the tree (that is, if not removed, the original parent and child relationships should be preserved). We can prove that there is a unique answer.

So the result should return the new root of the trimmed binary search tree. Note that the root node may change depending on a given boundary.

Example 1: 

Enter: root = [1.0.2], low = 1, high = 2Output:1.null.2]
Copy the code

Example 2: 

Enter: root = [3.0.4.null.2.null.null.1], low = 1, high = 3Output:3.2.null.1]
Copy the code

Example 3:

Enter: root = [1], low = 1, high = 2Output:1]
Copy the code

Example 4:

Enter: root = [1.null.2], low = 1, high = 3Output:1.null.2]
Copy the code

Example 5:

Enter: root = [1.null.2], low = 2, high = 4Output:2]
Copy the code

Tip:

  • The number of nodes in the tree is in range[1, 10] 内
  • 0 <= Node.val <= 10
  • Each node in the tree has a unique value
  • The title data guarantees that the input is a valid binary search tree
  • 0 <= low <= high <= 10

For this problem, we can use recursion.

  • If the current node is less than the lower bound, the pruned right subtree directly replaces the current node and returns.
  • If the current node is larger than the upper bound, replace the current node with the pruned left subtree and return.
  • If the current node is within the scope, we continue to recurse the left and right subtrees to find the node that is out of bounds.
/** * 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
 * @param {number} low
 * @param {number} high
 * @return {TreeNode}* /
var trimBST = function(root, low, high) {
    if(! root){return root
    }
    // If the current node is less than the lower bound, replace the current node with the pruned right subtree and return
    if(root.val < low){
        return trimBST(root.right, low, high)
    }
    // If the current node is larger than the upper bound, replace the current node with the pruned left subtree and return
    if(root.val > high){
        return trimBST(root.left, low, high)
    }

    // If the current node does not cross the boundary, continue recursion to the left and right subtrees
    root.left = trimBST(root.left, low, high)
    root.right = trimBST(root.right, low, high)
    return root
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the given number of tree nodes. We can access each node at most once.
  • Space complexity: O(n), where no extra memory is being used, but in the worst case the stack of recursive calls can be as large as the number of nodes.

(8) Delete nodes in the binary search tree

Given a root node root and a value key of a binary search tree, the nodes corresponding to key in the binary search tree are deleted, and the properties of the binary search tree are guaranteed to remain unchanged. Returns a reference to the root node of the binary search tree (which may be updated). Generally speaking, deleting a node can be divided into two steps:

  1. First find the node to delete;
  2. If it is found, delete it.

Note: The time complexity of the algorithm is required to be O(h), h is the height of the tree. Example:

root = [5.3.6.2.4.null.7]
key = 3
    5
   / \
  3   6
 / \   \
2   4   7The given value of the node to be deleted is3So we found it first3This node, and then delete it. One correct answer is [5.4.6.2.null.null.7], as shown in the figure below.5
   / \
  4   6
 /     \
2       7Another correct answer is [5.2.6.null.4.null.7].5
   / \
  2   6
   \   \
    4   7
Copy the code

We know that the left subtree of a binary search tree is always smaller than the root node, and the right subtree is always larger than the root node, so we can compare the value of the root node with the value of the key to be deleted to know where the value to be deleted is:

  • If the key is equal to the root node, then the current root node is deleted and the recursion exits.
  • If the key is larger than the root, then recurse to the right subtree;
  • If the key is smaller than the root, then the left subtree is recursively searched;

When we find the node to delete, there are four situations:

  • If the left and right child nodes of the node to be deleted are empty, the current node can be directly deleted.
  • If the left child node of the node to be deleted exists and the right child node is empty, the current node is set to the value of the left child node.
  • If the node to be deleted has a right child node and the left child node is empty, the current node is set to the value of the right child node.
  • In this case, we need to find the largest node smaller than the current node (or the smallest node larger than the current node) to replace the current node (in the code below, we are looking for the smallest node larger than the current node). 台湾国
/** * 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
 * @param {number} key
 * @return {TreeNode}* /
var deleteNode = function(root, key) {
    if(! root){return root
    }

    if(root.val > key){
        root.left = deleteNode(root.left, key)
    }else if(root.val < key){
        root.right = deleteNode(root.right, key)
    }else{
        if(! root.left && ! root.right){ root =null
        }else if(root.left && ! root.right){ root = root.left }else if(! root.left && root.right){ root = root.right }else if(root.left && root.right){
            let last = root.right
            while (last.left) {
                last = last.left
            }
            root.val = last.val
            root.right = deleteNode(root.right, last.val)
        }
    }
    return root

};
Copy the code

Complexity analysis:

  • Time complexity: O(logN). During the execution of the algorithm, we kept moving to the left or right of the tree. First, it takes O(H) time to find the node to delete. H refers to the height from the root node to the node to be deleted. Then it takes O(H) time to delete the node, where H refers to the height from the node to be deleted to the replacement node. Since O(H+ H)=O(H), H is the height of the tree, and if the tree is a balanced tree, H is logN.
  • Space complexity: O(H), the space used by the stack in recursion, where H is the height of the tree.

The common Ancestor of binary trees

(1) The most recent common ancestor of a binary tree

Given a binary tree, find the nearest common ancestor of the two specified nodes in the tree. The definition of recent public ancestor in Baidu Encyclopedia is: “For two nodes P and Q of the root tree T, the recent public ancestor is expressed as a node X, where x is the ancestor of P and Q and the depth of X is as large as possible (a node can also be its own ancestor).

For example, a given binary tree as follows: root = [3,5,1,6,2,0,8, null, null, 7, 4]

Example 1:

Enter: root = [3.5.1.6.2.0.8.null.null.7.4], p = 5, q = 1Output:3Explanation: Node5And the node1The most recent public ancestor of is the node3.Copy the code

Example 2:

Enter: root = [3.5.1.6.2.0.8.null.null.7.4], p = 5, q = 4Output:5Explanation: Node5And the node4The most recent public ancestor of is the node5. Because by definition the most recent common ancestor node can be the node itself.Copy the code

Description:

  • All nodes have unique values.
  • P and Q are different nodes and exist in a given binary tree.

For binary tree problems, often used is recursive traversal, here we also use recursion:

First, if the tree is empty or any section of P and q is equal to the root node, then the nearest common ancestor node of p and q is root node root.

If the tree is not empty and p and q are not equal to the root, then the left and right subtrees are recursively traversed:

  • If p and Q nodes exist in the nearest common ancestor nodes of the left and right subtrees, it means that P and Q are distributed in the left and right subtrees, and their nearest common ancestor node is root.
  • If only one subtree recursion has a result, that means both P and q are in the subtree, then return the result of the recursion for that tree.
  • If both subtrees recurse to null, indicating that neither P nor q is in the subtrees, then the root node root is returned.
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}* /
var lowestCommonAncestor = function(root, p, q) {
    if(! root || root === p || root === q){return root
    }

    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)
    
    if(! left)return right
    if(! right)return left

    return root
};
Copy the code

Complexity analysis:

  • Time complexity: O(n), where n is the number of binary tree nodes. We’re going through every node of the binary tree, so the time complexity is O(n).
  • Space complexity: O(n), where n is the number of binary tree nodes. The stack depth of the recursive call depends on the height of the binary tree, which in the worst case is a chain, which in this case has a height of n, so the space complexity is O(n).

(2) The most recent common ancestor of the binary search tree

Given a binary search tree, find the nearest common ancestor of the two specified nodes in the tree.

The definition of recent public ancestor in Baidu Encyclopedia is: “For two nodes P and Q of the root tree T, the recent public ancestor is expressed as a node X, where x is the ancestor of P and Q and the depth of X is as large as possible (a node can also be its own ancestor).

For example, given the following binary search tree: root = [6,2,8,0,4,7,9, null, null, 3, 5)

Example 1:

Enter: root = [6.2.8.0.4.7.9.null.null.3.5], p = 2, q = 8Output:6Explanation: Node2And the node8The most recent common ancestor of6.Copy the code

Example 2:

Enter: root = [6.2.8.0.4.7.9.null.null.3.5], p = 2, q = 4Output:2Explanation: Node2And the node4The most recent common ancestor of2Because the most recent common ancestor node can be the node itself by definition.Copy the code

Description:

  • All nodes have unique values.
  • P and Q are different nodes and exist in the given binary search tree.

For this problem, we can use recursion or iteration.

1) Recursive implementation: for binary tree search tree:

  • If p.val and q.val are both smaller than root.val, then p and q must be in the left subtree of root;
  • If p.val and q.val are both larger than root.val, then p and q must be in the right subtree of root;
  • Val = root; var = root; var = root; var = root; var = root; 台湾国

We can use a while loop that terminates when root is null:

  • Val =root. Left =root. Left =root.
  • If p.val and q.val are both larger than root.val, then p and q must be in the right subtree of root, root=root.right, traversing to the right subnode of root.
  • In other cases, the current root is the most recent public ancestor, ending the traversal and ending the loop directly.

Recursive implementation:

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /

/ * * *@param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}* /
var lowestCommonAncestor = function(root, p, q) {
    if(p.val < root.val && q.val < root.val){
        return lowestCommonAncestor(root.left, p, q)
    }
    if(p.val > root.val && q.val > root.val){
        return lowestCommonAncestor(root.right, p, q)
    }
    return root
};
Copy the code

Iterative implementation:

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /

/ * * *@param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}* /
var lowestCommonAncestor = function(root, p, q) {
    while(root){
        if(p.val < root.val && q.val < root.val){
            root = root.left
        }else if(p.val > root.val && q.val > root.val){
            root = root.right
        }else{
            break}}return root
};
Copy the code

Iterative complexity analysis:

  • Time complexity: O(n), where n is the number of nodes in the binary search tree. In the worst case, we need to go through the whole tree depth-first;
  • Space complexity: O(1), we only need constant space to operate.

Recursive complexity analysis:

  • Time complexity: O(n), where n is the number of nodes in the binary search tree. In the worst case, we need to go depth-first through the whole binary tree;
  • Space complexity: O(n), we need to recursively traverse the tree, so space complexity is O(n);