Binary tree recursive algorithm problem (classical algorithm problem JavaScript recursive implementation, continuous output)

“This is the second day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

The role of binary trees

Understand the basics of high-level data structures

Graph of TD binary tree - > complete binary tree Binary tree - > how tree/binary tree forest - > binary sort tree Complete binary tree > pile of full binary tree -- - > priority queue how tree/forest tree -- > dictionary More tree/forest -- > AC automata tree/forest --> set binary sort tree --> AVL tree binary sort tree --> 2-3 tree binary sort tree --> red black tree multi-fork sort tree --> B -- tree /B+ tree

Heap and priority queue are the best tools to maintain the maximum value of collection

Dictionary tree and AC automata are the most powerful tools for string and its related conversion problems

And collection is the magic weapon for connectivity problems

AVL tree, 2-3 tree and red-black tree are the basic implementation of important data retrieval containers in the language standard library

B- tree and B+ tree are important data structures at the bottom of file system and database

The best way to practice your recursive skills

Design/understand recursive programs

1. Mathematical induction -> structural induction
2. Give recursive functions an explicit meaning
3. Thinking about boundary conditions
4. Implement the recursive process

• K0 is correct
• Let’s say ki -> ki+1
• k0 -> k1 -> … kn-1 -> kn

function fib(n) {  //fib(n) represents the value of the NTH Fibonacci sequence
    if (n <= 2) return n;  / / k0 is correct
    return fib(n-1) + f(n-2);  // Assume that ki is correct
}
Copy the code

Left child right brother notation saves space

Binary tree algorithm (recursive)

Antecedent traversal of binary tree -144

Give you the root node of the binary tree, root, and return a pre-traversal of its node value.

Example 1:

Input: root = [1, NULL,2,3] Output: [1, 3] Example 2:

Input: root = [] Output: []

Example 3:

Input: root = [1] Output: [1]

Example 4:

Input: root = [1,2] output: [2]

Example 5:

Input: root = [1, NULL,2]

const preorder = function(root, arr) {
    if(! root)return;
    arr.push(root.val)
    preorder(root.left, arr)
    preorder(root.right, arr)
}

const preorderTraversal = function(root) {
    const arr = []
    preorder(root, arr);
    return arr;
};
Copy the code

N Preorder traversal of the fork tree -589

/ * * *@param {Node|null} root
 * @return {number[]}* /
const preorder = function(root) {
    let arr = [];
    preorderFunc(root, arr)
    return arr
};


const preorderFunc = function(root, arr) {
    if(! root)return;
    arr.push(root.val);
    if (root.children) {
        root.children.forEach(item= > {            
            preorderFunc(item, arr)
        })
    }
}
Copy the code

Flip the binary tree -226

1. Function Meaning: Invert the binary tree with root node
2. Boundary condition: no need to flip when root is empty
3. Recursion: Flip the left subtree of root and flip the right subtree of root

/** * 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 null;
    let tempNode = invertTree(root.left);
    root.left = invertTree(root.right);
    root.right = tempNode;
    return root;
};
Copy the code

Finger Offer 32-ii. Print binary tree II from top to bottom

1. Function meaning: Put the value of each node into the appropriate layer (need to record the number of layers)
2. Boundary condition: No value is required when root is null
3. Recursive process: first put the current node value, then put the left and right nodes in the next level of the array

Recursive solution:

const levelOrder = function(root) {
    let arr = []
    _levelOrder(root, arr, 0)
    return arr
};

const _levelOrder = function(root, arr, i) {
    if(! root)return;
    arr[i] ? arr[i].push(root.val) : arr[i] = [root.val];
    _levelOrder(root.left, arr, i+1)
    _levelOrder(root.right, arr, i+1)}Copy the code

Queue solution:

const levelOrder = function (root) {
    if(! root)return []
    const queue = [root];
    const arr = [];

    while (queue.length > 0) {
        const temp = [];
        let i = queue.length
        for(; i >0; i--) {
            const node = queue.shift();
            temp.push(node.val)
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        arr.push(temp)
    }
    return arr
};
Copy the code

107. Sequence traversal of binary trees II

Similar to finger Offer 32-ii. Print binary tree II from top to bottom, just flip the array.

const levelOrderBottom = function(root) {
    const result = [];
    _levelOrderBottom(root, result, 0);
    
    / / tips
    for(let i=0, j = result.length - 1; i < j; i++, j--) {
        const temp = result[j];
        result[j] = result[i];
        result[i] = temp;
    }
    return result;
    //return result.reverse()
};

const _levelOrderBottom = function(root, arr, idx) {
    if(! root)return;
    arr[idx] ? arr[idx].push(root.val) : arr[idx] = [root.val];
    root.left && _levelOrderBottom(root.left, arr, idx + 1);
    root.right && _levelOrderBottom(root.right, arr, idx + 1);
}
Copy the code

103. Serrated sequence traversal for binary trees

Again, as long as the odd number of layers are flipped

/** * 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[][]}* /
const zigzagLevelOrder = function (root) {
    const result = [];
    _zigzagLevelOrder(root, result, 0);
    for (let i = 1; i < result.length; i += 2) {
        result[i] = result[i].reverse()
    }
    return result
};

const _zigzagLevelOrder = function (root, arr, idx) {
    if(! root)return;
    arr[idx] ? arr[idx].push(root.val) : arr[idx] = [root.val];
    root.left && _zigzagLevelOrder(root.left, arr, idx + 1);
    root.right && _zigzagLevelOrder(root.right, arr, idx + 1);
}
Copy the code

110. Balanced binary trees

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

const getHeight = (root) = > {
    if(! root)return 0;
    const left = getHeight(root.left);
    const right = getHeight(root.right);
    // If the left and right absolute values are greater than 1, it is not balanced
    if (Math.abs(left - right) > 1) return -2;
    // If the left or right subtrees are less than 0, there is an imbalance
    if (left < 0 || right < 0) return -2;
    // Return the higher value of the left and right subtrees +1= the current node height
    return Math.max(left, right) + 1;
}
Copy the code

112. Sum 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}* /
const hasPathSum = function(root, targetSum) {
    if(! root)return false;
    // If it is a leaf node, determine whether the current value is the target value
    if(! root.left && ! root.right)return root.val === targetSum;
    return hasPathSum(root.left, targetSum - root.val) 
    || hasPathSum(root.right, targetSum - root.val);
};
Copy the code

105. Construct a binary tree by traversing pre-order and middle-order sequences

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}* /
const buildTree = function (preorder, inorder) {
    if(! preorder.length)return null;

    const result = new TreeNode();
    const root = preorder.shift();
    result.val = root;
    let inIdx = 0;
    while(inorder[inIdx] ! == root) inIdx++;const leftPre = preorder.slice(0, inIdx);
    const rightPre = preorder.slice(inIdx);
    const leftIn = inorder.slice(0, inIdx);
    const rightIn = inorder.slice(inIdx + 1);

    result.left = buildTree(leftPre, leftIn);
    result.right = buildTree(rightPre, rightIn);
    return result;
};
Copy the code

222. Number of nodes in a complete 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 countNodes = function(root) {
    if(! root)return 0;
    return 1 + countNodes(root.left) + countNodes(root.right)
};
Copy the code

The KTH largest node in the binary search tree

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

Note: binary search tree, the left node must be smaller than the right node. That is, the middle order traversal of a binary search tree must be an ordered array.

First calculate the number of the right node and determine the position of the KTH node. Go to the

/** * 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}* /
const kthLargest = function(root, k) {
    const r_count = countTree(root.right);
    if (k <= r_count) return kthLargest(root.right, k);
    if (k === r_count + 1) return root.val;
    return kthLargest(root.left, k - r_count - 1);
};

const countTree = (root) = > {
    if(! root)return 0;
    return countTree(root.left) + countTree(root.right) + 1;
}
Copy the code

Offer 26. Substructure of tree

Input two binary trees A and B to determine whether B is A substructure of A. (Convention that an empty tree is not a substructure of any tree)

B is A substructure of A, that is, A has the same structure and node value as B.

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}* /
 // check whether it is a subtree
const isSubStructure = function(A, B) {
    if(! B || ! A)return false;
    if (B.val === A.val && is_Match(A,B)) return true;   
    return isSubStructure(A.left, B) || isSubStructure(A.right, B)
};

// Check whether the nodes match
const is_Match = (A, B) = > {
    if(! B)return true;
    if(! A)return false;
    if(B.val ! == A.val)return false;
    return is_Match(A.left, B.left) && is_Match(A.right, B.right);
}

Copy the code