Three, special binary tree problem

2020.11.27

No.101 Symmetric binary trees

Given a binary tree, check whether it is mirror symmetric.

 

For example, a binary tree [1,2,2,3,4,4,3] is symmetric.

1/2 2 / \ / 3 4 4 3

But the following [1,2,2,null,3,null,3] is not mirror symmetric:

1/2 2\3 3

Advanced:

Can you solve this problem both recursively and iteratively?

Source: LeetCode link: leetcode-cn.com/problems/sy… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution a:

/* * @lc app=leetcode.cn id=101 lang=javascript * * [101] Symmetric binary tree */

// @lc code=start
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @return {boolean}* /
var isSymmetric = function(root) {
    // In order traversal + layers
    const inorderLevelTraversal = function(root) {
        const r = [];
        const recurse = ( node, n ) = > {
            if(! node)return;
            n++;
            recurse(node.left, n);
            r.push([node.val,n])
            recurse(node.right, n);
        };

        recurse(root, 0);
        return r;
    };
    const r = inorderLevelTraversal(root);
    console.log('r', r);
    // Determine whether the order traversal group is symmetric
    let p1 = 0,
        p2 = r.length - 1;
    while( p1 < p2 ) {
        if( r[p1][0] != r[p2][0] || r[p1][1] != r[p2][1])return false;
        p1++;
        p2--;
    };
    return true;
};
Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=101 lang=javascript * * [101] Symmetric binary tree */

// @lc code=start
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @return {boolean}* /
const isSymmetric = (root) = > {
  
  const check = (left, right) = > {
    if (left == null && right == null) { // Both subtrees are null and are symmetric
      return true;
    }
    if (left && right) {  // If both subtrees exist, they must have the same root value and their subtrees must be mirrored
      return left.val == right.val && check(left.left, right.right) && check(left.right, right.left);
    }
    return false;         // If a subtree exists and a subtree does not exist, it must be asymmetric
  };

  if (root == null) {     // If null is passed in as root, it is symmetric
    return true;
  }           
  return check(root.left, root.right); // If not, determine whether the left and right subtrees satisfy symmetry
};
Copy the code

Solution 3:

/* * @lc app=leetcode.cn id=101 lang=javascript * * [101] Symmetric binary tree */

// @lc code=start
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @return {boolean}* /
const isSymmetric = (root) = > {
  if (root == null) return true; 

  const queue = [];
  queue.push(root.left, root.right);  // Start with two subtrees

  while (queue.length) {  // When the queue is empty, there are no nodes left
    const levelSize = queue.length; // Number of nodes at the current layer
    for (let i = 0; i < levelSize; i += 2) { // The nodes of the current layer are listed in pairs
      const left = queue.shift();   
      const right = queue.shift();  // List a pair of nodes
      if ((left && right == null) || (left == null && right)) { // There is a existence and there is a non-existence
        return false;
      }
      if (left && right) { // Both exist
        if(left.val ! = right.val) {// The value of the node is different
          return false;
        }
        queue.push(left.left, right.right); // Push a pair of nodes from the next layer
        queue.push(left.right, right.left); // Push a pair of nodes from the next layer}}}return true; // return true if false is not returned
};
Copy the code

There are three solutions: 1. Refer to the sequence traversal idea in the sequence traversal to determine whether the array after the sequence traversal is symmetric, and add layers here to avoid the situation that a node is null and cannot be judged; 2. 2, DFS recursion, direct recursive judgment; 3. BFS iteration, maintain a queue for judgment

2020.11.30

Balanced binary trees

Given a binary tree, determine whether it is a highly balanced binary tree.

In this case, a highly balanced binary tree is defined as:

The absolute value of the height difference between the left and right subtrees of each node of a binary tree does not exceed 1.

 

Example 1:

Input: root = [3,9,20,null,null,15,7] output: true example 2:

Input: root = [1,2,2,3,3,null,null,4,4] output: false

Input: root = [] Output: true

Tip:

The number of nodes in the tree is in the range [0, 5000] -104 <= node. val <= 104

Source: LeetCode link: leetcode-cn.com/problems/ba… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution a:

/* * @lc app=leetcode.cn id=110 lang=javascript * * [110] Balanced binary tree */

// @lc code=start
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {boolean}* /
var isBalanced = function(root) {
    // Get the height of the tree
    const getTreeHeight = tree= > {
        if(! tree)return true;
        return 1 + Math.max(getTreeHeight(tree.left),getTreeHeight(tree.right))
    };
    // Return the result after the difference comparison
    if(! root)return true;
    const lh = getTreeHeight(root.left),
          rh = getTreeHeight(root.right);
    // If the result has a direct false greater than 1
    if(Math.abs(lh-rh) > 1 ) {
        return false;    
    }
    return isBalanced(root.left) && isBalanced(root.right);
};
Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=110 lang=javascript * * [110] Balanced binary tree */

// @lc code=start
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {boolean}* /
var isBalanced = function(root) {
    // Determine whether it is balanced
    const balanced = function (node) {
        if(! node)return 0
        const left = balanced(node.left)
        const right = balanced(node.right)
        if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
            return -1
        }
        return Math.max(left, right) + 1
    }
    returnbalanced(root) ! = = -1;
};
Copy the code

There are two options: 1, top down: get left subtree and right subtree height comparison, if not directly return false, otherwise downward recursion; 2, from the bottom up: similar to the sequential traversal scheme, first judge the left subtree, then judge the right subtree, then judge the root node, if there is no match return false, otherwise recursion upward

2020.12.01

No.226 Flip binary trees

Flip a binary tree.

Example:

Input:

4/2 7 / \ / 1 3 6 9 output:

4/7 2 / \ / 9 6 3 1 Note: This question is inspired by Max Howell’s original question:

Google: It’s too bad that 90% of our engineers use your software (Homebrew), but you can’t write a flip binary tree on a whiteboard during an interview.

Source: LeetCode link: leetcode-cn.com/problems/in… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution a:

/* * @lc app=leetcode.cn id=226 lang=javascript * * [226] Reverse binary tree */

// @lc code=start
/** * 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) {
    let temp = null;
    const recurse = node= > {
        if(! node)return;
        temp = node.left;
        node.left = node.right;
        node.right = temp;
        recurse(node.left);
        recurse(node.right);
    };
    recurse(root);
    return root;
};
Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=226 lang=javascript * * [226] Reverse binary tree */

// @lc code=start
/** * 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;
  const queue = [root];   // Maintain a queue, initially pushed to layer 1 root
  
  while (queue.length) {
    const cur = queue.shift(); // Out of the column node
    [cur.left, cur.right] = [cur.right, cur.left]; // Swap the left and right subtrees

    cur.left && queue.push(cur.left);
    cur.right && queue.push(cur.right);
  }
  
  return root;
};
Copy the code

There are two schemes for the most common questions in the interview tree: 1. Recursion; 2. 2, iterations,

2020.12.02

No.617 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: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 Output: Merged Tree: 3/4 5 / \ \ 5 4 7 Note: The merge must start at the root of both trees.

Source: LeetCode link: leetcode-cn.com/problems/me… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution a:

/* * @lc app=leetcode.cn id=617 lang=javascript * * [617] Merge binary tree */

// @lc code=start
/** * 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) {
    // Use t1 as the baseline
    if(! t1)return t2;
    if(! t2)return t1;
    t1.val = t2.val + t1.val;
    t1.left = mergeTrees(t1.left, t2.left);
    t1.right = mergeTrees(t1.right, t2.right);
    return t1;
};
Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=617 lang=javascript * * [617] Merge binary tree */

// @lc code=start
/** * 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) {
    // Use t1 as the baseline
    if(! t1)return t2;
    if(! t2)return t1;
    t1.val = t2.val + t1.val;
    // Construct stack space iteration
    const stack = [[t1, t2]];
    while (stack.length) {
        const [p, q] = stack.shift();
        if (p.left && q.left) {
            p.left.val += q.left.val
            stack.push([p.left, q.left]);
        } else if(! p.left) p.left = q.left;else if(! q.left) q.left = p.left;if (p.right && q.right) {
            p.right.val += q.right.val;
            stack.push([p.right, q.right]);
        } else if(! p.right) p.right = q.right;else if(! q.right) q.right = p.right; }return t1;
};
Copy the code

As 226, the basic operation of the tree, the interview tree is often tested, there are two schemes: 1. Recursion; 2. 2, iterations,

2020.12.03

No.654 The most binary tree

Given an array of integers with no repeating elements. A maximum binary tree built from this array is defined as follows:

The root of a binary tree is the largest element in the array. The left subtree is the largest binary tree constructed from the left of the maximum value in the array. The right subtree is the largest binary tree constructed from the right-hand side of the maximum value of the array. Build the maximum binary tree from the given array and output the root node of the tree.

 

Example:

Input: [3,2,1,6,0,5]

6/3 5 \ / 2 0 1

Tip:

The size of the given array is between [1, 1000].

Source: LeetCode link: leetcode-cn.com/problems/ma… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution:

/* * @lc app=leetcode.cn id=654 lang=javascript * * [654] Max binary tree */

// @lc code=start
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {number[]} nums
 * @return {TreeNode}* /
var constructMaximumBinaryTree = function(nums) {
    if(nums.length == 0) return null;
    const root = new TreeNode(Math.max(... nums)); root.left = constructMaximumBinaryTree(nums.slice(0,nums.indexOf(Math.max(... nums)))); root.right = constructMaximumBinaryTree(nums.slice(nums.indexOf(Math.max(... nums))+1));
    return root;
};
Copy the code

Typical recursive problem, with the maximum value as the split point

2020.12.04

No.655 Output binary tree

Print a binary tree in an M *n two-dimensional string array, following the following rules:

The number of rows m should be equal to the height of the given binary tree. The number of columns n should always be odd. The value of the root node (given in string format) should be in the middle of the first line that can be placed. The row and column of the root node divides the remaining space into two parts (lower left and lower right). You should print the left subtree in the lower left section and the right subtree in the lower right section. The lower left and lower right parts should have the same size. Even if one subtree is empty and the other is not, you don’t need to output anything for the empty subtree, but you still need to leave enough space for the other subtree. However, if both subtrees are empty, no space needs to be left for them. Each unused space should contain an empty string “”. Output subtrees using the same rules. Example 1:

Input: 1/2 output: [[” “, “1”, “”], [” 2″, “”,” “]] example 2:

Input: 1/2, 3, 4, output: [[” “, “”,” “, “1”, “”,” “, “”], [” “,” 2 “, “”,” “, “”,” 3 “, “”], [” “,” “, “4”, “”,” “, “”,” “]] example 3:

Input: 1/2 5/3/4 Output: [[” “, “”,” “, “”,” “, “”,” “, “1”, “”,” “, “”,” “, “”,” “, “”] [” “,” “, “”,” 2 “, “”,” “, “”,” “, “”,” “, “”,” 5 “, “”, “”,” “] [” “, “3”, “”,” “, “”,” “, “”,” “, “”,” “, “”,” “, “”,” “, “”] [” 4″, “”,” “, “”,” “, “”,” “, “”,” “, “”,” “, “”, “”, “”, “”]] note: the height of the binary tree is in the range [1, 10].

Source: LeetCode link: leetcode-cn.com/problems/pr… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution:

/* * @lc app=leetcode.cn id=655 lang=javascript * * [655] Output binary tree */

// @lc code=start
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @return {string[][]}* /
var printTree = function(root) {
    // Get the height of the tree
    const treeHeight = root= > {
        if(! root)return 0;
        return treeHeight(root.left) > treeHeight(root.right) ? ( treeHeight(root.left) + 1 ): (treeHeight(root.right) + 1);
    };
    // Fill in the output values
    const printValue = (r, root, n, left, right ) = > {
        if(root) {
        let mid = Math.floor( ( left + right ) / 2 );
        r[n][mid] = root.val + ' ';
        printValue(r, root.left, n+1, left, mid);
        printValue(r, root.right, n+1, mid+1, right)}
    };

    const m = treeHeight(root),
          n = Math.pow(2,m) - 1;
    console.log(m)
    const r = new Array(m);
    for(let i=0; i<m; i++) r[i]=new Array(n).fill(' ');
    printValue(r, root,0.0,n);
    return r;
};
Copy the code

The dichotomy recurses, mister into a two-dimensional array, and then fills in the corresponding position

2020.12.06

No.998 Most Binary tree – II

Maximum tree definition: a tree in which the value of each node is greater than any other value in its subtree.

Give the root node root of the largest tree.

As in the previous problem, the given tree is constructed recursively from table A (root = Construct(A)) using the following Construct(A) routine:

If A is empty, return null. Otherwise, let A[I] be the largest element of A. The left subtree of root will be constructed as Construct([A[0], A[1]…, A[i-1]]). The right subtree of root will be constructed as Construct([A[I +1], A[I +2], …, A[a.length-1]]) Construct(A)

Suppose B is A copy of A with the added value of val. Make sure that the values in B are different.

Returns the Construct (B).

 

Example 1:

Input: root = [4,1,3, null, null, 2], val = 5 output: [5, 4, null, 1, 3, null, null, 2] : A =,4,2,3 [1], B =,4,2,3,5 [1] example 2:

Input: root = [5 4-trichlorobenzene, null, 1], val = 3 output: [5 4-trichlorobenzene, null, 1, null, 3] : A =,1,5,4 [2], B =,1,5,4,3 [2] example 3:

Input: root = (5, 2, 3, null, 1], val = 4 output: [5 4-trichlorobenzene, null, 1, 3] : A =,1,5,3 [2], B =,1,5,3,4 [2]

Tip:

1 <= B.length <= 100

Source: LeetCode link: leetcode-cn.com/problems/ma… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution:

/* * @lc app=leetcode.cn id=998 lang=javascript * * [998] Max Binary tree II */

// @lc code=start
/** * 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}* /
var insertIntoMaxTree = function(root, val) {
    // In order traversal
    const inorderTraversal = function(root) {
        let r = [];
        // Recursive function
        const recurse = root= > {
            // Recursive termination condition
            if(! root)return;
            // First traverse the left subtree
            recurse(root.left);
            // When a terminating condition is encountered, val is the value that meets the terminating condition
            r.push(root.val);
            // Iterate through the right subtree again
            recurse(root.right);
        };
        recurse(root);
        return r;
    };

    // The largest binary tree of the array
    const constructMaximumBinaryTree = function(nums) {
        if(nums.length == 0) return null;
        const root = new TreeNode(Math.max(... nums)); root.left = constructMaximumBinaryTree(nums.slice(0,nums.indexOf(Math.max(... nums)))); root.right = constructMaximumBinaryTree(nums.slice(nums.indexOf(Math.max(... nums))+1));
        return root;
    };

    const A = inorderTraversal(root);
    A.push(val);
    return constructMaximumBinaryTree(A);
};
Copy the code

Sum of questions 94 and 655, first find the order traversal group, add the value val after the array, and find the maximum tree for the new array

Conclusion:

  1. Special binary tree is mainly a tree of different forms of processing, the common is mainly recursion and iteration, the interview is often required to write out;
  2. Obtaining trees according to different requirements is a basic investigation of trees. If trees are tested in the interview process, special binary trees are generally used to test