Data structure – binary tree

1. Front, middle and back traversal of the binary tree

1. In the sequence traversal

 var inorderTraversal = function (root, array = []) {
     if(root){
         inorderTraversal(root.left, array);
         array.push(root);
         inorderTraversal(root.right, array);
     }
     return array;
 }
Copy the code

2. The former sequence traversal

    var preorderTraversal = function (root, array = []) {
      if (root) {
        array.push(root.val);
        preorderTraversal(root.left, array);
        preorderTraversal(root.right, array);
      }
      return array;
    };
Copy the code

3. After the sequence traversal

    var postorderTraversal = function (root, array = []) {
     if (root) {
       postorderTraversal(root.left, array);
       postorderTraversal(root.right, array);
       array.push(root.val);
     }
     return array;
   };
Copy the code

2. Mirror image of the binary tree

Operates on the given binary tree to transform it into a mirror image of the source binary tree.

For example: source binary tree 8 / \ 6 10 / \ / \ 57 9 11 Mirror binary tree 8 / \ 10 6 / \ / 11 9 7 5Copy the code

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {void}* /
var mirror = function(root) {
   if(! root)return ;
   mirror(root.left);
   mirror(root.right);
   let tmp = root.left;
   root.left = root.right;
   root.right = tmp;
   
};
Copy the code

I’ll just write it recursively

3. The depth of the binary tree

Enter the root of a binary tree and find the depth of the tree.

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @return {number}* /
var treeDepth= function(root) {
    if(! root)return 0;
    return Math.max(treeDepth(root.left), treeDepth(root.right)) + 1;
};
Copy the code

4. Balanced binary trees

Enter the root of a binary tree to determine whether the tree is a balanced binary tree.

A binary tree is a balanced binary tree if the depth difference between the left and right subtrees of any node is no more than 1.

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @return {boolean}* /
var isBalanced = function(root) {
    
    let ans = true;
    dfs(root);
    
    function dfs(root) {
        if(! root)return 0;
        let left = dfs(root.left), right = dfs(root.right);
        if(Math.abs(left-right) > 1) ans = false;
        return Math.max(left, right) + 1;
    }    
    
    return ans;
};
Copy the code

5. Print multiple lines of binary tree

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @return {number[][]}* /
var printFromTopToBottom = function(root) {
    if(! root)return [];
    const q = [root];
    const res = [];
    let level = 0;
    while(q.length) {
        res[level] = [];
        let size = q.length;
        for(let i = 0; i < size; i ++) {
            const t = q.shift();
            res[level].push(t.val);
            if(t.left) q.push(t.left);
            if(t.right) q.push(t.right);
        }
        level ++;
    }
    
    return res;
};
Copy the code

6. Symmetric binary trees

/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } * /
function isSymmetrical(pRoot)
{
    // write code here
    function dfs(p1, p2){
        if(! p1 && ! p2)return true;
        if(! p1 || ! p2)return false;
        if(p1.val ! == p2.val)return false;
        return dfs(p1.left,p2.right) && dfs(p1.right, p2.left);
    }
    
    if(! pRoot)return true;
    else return dfs(pRoot.left, pRoot.right);
}
Copy the code

7. Next node in the binary tree

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = this.father = null; *} * /
/ * * *@param {TreeNode} p
 * @return {TreeNode}* /
var inorderSuccessor = function(p) {
    if(! p)return null;
    // Case 1 has a right subtree
    if(p.right){
        p = p.right;
        while(p.left){
            p = p.left;
        }
        return p;
    }
    
    // 2. No right subtree
    while(p.father){
        if(p.father.left === p){
            return p.father;
        }
        p = p.father;
    }
    
    return null;
};
Copy the code

8. Print the binary tree from top to bottom

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var printFromTopToBottom = function(root){
    const res = []
    if(! root)return res
    const q = [root]
    while(q.length) {
        const node = q.shift()
        res.push(node.val)
        node.left && q.push(node.left)
        node.right && q.push(node.right)
    }
    return res
}
Copy the code

9. Binary tree paths with a neutral value

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}* /
var findPath = function(root, sum) {
    const path = []
    const ans = []
    function dfs(root, sum) {
        if(! root)return
        path.push(root.val)
        sum -= root.val
        if(! root.left && ! root.right && ! sum) ans.push([...path]) dfs(root.left,sum) dfs(root.right,sum) path.pop() } dfs(root,sum)return ans
};
Copy the code

10. Rebuild the binary tree

/** * 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(! preorder.length || ! inorder.length)return null;
  
  const rootVal = preorder[0];
  const node = new TreeNode(rootVal);
  
  
  let i = 0;
  for(; i < inorder.length; i++){
      if(inorder[i] === rootVal) break;
  }
  
  node.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i)); // The number of first I in the preceding order
  node.right = buildTree(preorder.slice(i + 1), inorder.slice(i+1));
  
  return node;
  
};
Copy the code

11 Print the binary tree in glyph order

/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } * /
function Print(pRoot)
{
    // write code here
    const res = [];
    if(! pRoot)return res;
    const q = [pRoot];
    let level = 0;
    while(q.length) {
        res[level] = []
        let size = q.length;
        for(let i = 0; i < size; i++){
            const t = q.shift();
            if(level % 2= = =0) res[level].push(t.val);
            else res[level].unshift(t.val)
            if(t.left) q.push(t.left)
            if(t.right) q.push(t.right)
        }
        level ++;
    }
    
    return res;
}
Copy the code

12 Subsequent traversal sequences of binary search trees

/ * * *@param {number[]} sequence
 * @return {bool}* /
var verifySequenceOfBST = function(sequence) {
  function dfs(l,r) {
    if (l >= r) return true
    let root = sequence[r]
    let k = l
    while(k < r && sequence[k] < root) k++
    for(let i = k; i < r; i ++) {
        if(sequence[i] < root){
            return false}}return dfs(l,k-1) && dfs(k,r-1)}return dfs(0, sequence.length-1)};Copy the code

13 Tree substructure

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} pRoot1
 * @param {TreeNode} pRoot2
 * @return {boolean}* /
var hasSubtree = function(pRoot1, pRoot2) {
    
    function isPart (p1, p2) {
        if(! p2)return true;
        if(! p1 || p1.val ! = p2.val)return false;
        return isPart(p1.left,p2.left) && isPart(p1.right,p2.right);
        
    }
    
    if(! pRoot1 || ! pRoot2)return false;
    if (isPart(pRoot1, pRoot2)) return true;
    return hasSubtree(pRoot1.left, pRoot2) || hasSubtree(pRoot1.right, pRoot2);
    
};
Copy the code

14 Serialize the binary tree

/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } * /
function Serialize(pRoot)
{
    // write code here
    return JSON.stringify(pRoot)
}
function Deserialize(s)
{
    // write code here
    return JSON.parse(s)
}
Copy the code

Copy the code

The KTH element of the binary search tree

/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } * /
function KthNode(pRoot, k)
{
    // write code here
    if(k < 0| |! pRoot)return null;
    let ans = [];
    function dfs(root){
        if(root){
            dfs(root.left);
            ans.push(root);
            dfs(root.right);
        }
    }
    
    dfs(pRoot);
    return ans[k-1];
}
Copy the code

LeetCode111 minimum depth of binary tree

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number}* /
var minDepth = function(root) {

    return dfs(root);
    function dfs(root){
        if(! root)return 0;
        if(root.left && ! root.right)return dfs(root.left) + 1;
        if(! root.left && root.right)return dfs(root.right) + 1;
        return Math.min(dfs(root.left), dfs(root.right)) + 1; }};Copy the code

Middle order traversal of LeetCode97 binary tree

A recursive version

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var inorderTraversal = function(root) {
    const res = [];
    dfs(root);

    return res;

    function dfs(root){
        if(root){ dfs(root.left); res.push(root.val); dfs(root.right); }}; };Copy the code

Non-recursive version

const inorderTraversal = (root) = > {
  const res = [];
  const stack = [];

  while (root) {        // all left child nodes that can be pushed are pushed in
    stack.push(root);
    root = root.left;
  }
  while (stack.length) {
    let node = stack.pop(); // The node at the top of the stack goes off
    res.push(node.val);     // Process the numeric part of the right subtree before pressing into it (because of middle-order traversal)
    node = node.right;      // Get its right subtree
    while (node) {          // Right subtree exists, execute while loop
      stack.push(node);     // Press the current root
      node = node.left;     // Press into the left child}}return res;
};
Copy the code

LeetCode112 Total of paths

/** * 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} targetSum
 * @return {boolean}* /
var hasPathSum = function(root, targetSum) {
    if(! root)return false;
    let res = false;
    const dfs = (n, s) = > {
        // console.log(n.val, s);
        if(! n.left && ! n.right && s === targetSum) res =true; 
        if(n.left) dfs(n.left, s + n.left.val);
        if(n.right) dfs(n.right, s + n.right.val);
    }
    dfs(root, root.val);
    return res;
};
Copy the code

It is interesting to