basis

concept

A binary tree is a tree-like data structure with at most two subtrees per node.

Common traversal order

  • Depth traversal

    Front order: middle → left → right

    Middle order: left → middle → right

    After order: left → right → middle (traversal used when deleting binary tree)

  • Breadth traversal

    Order traversal (you can also use the idea of depth traversal)

Traverse the parsing

The tree structure is defined first, and the subsequent traversal functions are based on this input

/** * 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[]}* /
Copy the code

The former sequence traversal

A recursive version

var preorderTraversal = function(root) {
    let result = []
    var preOrderTraverseNode = (node) = > {
        if(node) {
            // Start the root node
            result.push(node.val)
            // Then traverse the left subtree
            preOrderTraverseNode(node.left)
            // Walk through the right subtree again
            preOrderTraverseNode(node.right)
        }
    }
    preOrderTraverseNode(root)
    return result;
};

Copy the code

Non-recursive version

// Use stack assist
const preOrderTraverseUnRecur = (root) = > {
    let res = [];
    let stack = [root];
    let node = null;

    while(stack.length ! = =0) {
        node = stack.pop();
        // The first step is to access the root node
        res.push(node.val);

        if(node.right) {
            stack.push(node.right)
        }

        // Since pop is fetching the last element, we need to make sure that the left node is fetched first
        if(node.left) {
            stack.push(node.left)
        }
    }
		return res;
}
Copy the code

In the sequence traversal

A recursive version

var inorderTraversal = function(root) {
    let result = []
    var preOrderTraverseNode = (node) = > {
        if(node) {
            preOrderTraverseNode(node.left);
            result.push(node.val);
            preOrderTraverseNode(node.right);
        }
    }
    preOrderTraverseNode(root)
    return result;
};
Copy the code

Non-recursive version

function inorderTraversal (root) {
    let res = [];
    let stack = [];
    while(stack.length > 0 || root){
        if(root){
            stack.push(root);
            root = root.left;
        } else {
            root = stack.pop();
            if(root.val) res.push(root.val); root = root.right; }}return res;
}
Copy the code

After the sequence traversal

A recursive version

var inorderTraversal = function(root) {
    let result = []
    var preOrderTraverseNode = (node) = > {
        if(node) {
            preOrderTraverseNode(node.left)
            preOrderTraverseNode(node.right)
            result.push(node.val)
        }
    }
    preOrderTraverseNode(root)
    return result;
};
Copy the code

Non-recursive version

var postorderTraversal = function(root) {
    let res = [];
    let stack = [];
    if(root) stack.push(root);
    while(stack.length){
        root = stack.pop();
        if(root.val) res.unshift(root.val);
        if(root.left) stack.push(root.left);
	if(root.right) stack.push(root.right);
    }
    return res;
};

// The following is the same as the following:
// The trailing traversal is the left and right root
// The forward traversal is root left and right
// If we change list.push(node.val) to list.unshift(node.val), then we change the traversal order from left to right roots to right and left roots
// Then we just need to change the right and left roots to the left and right roots to complete the sequence
Copy the code

application

Common survey questions

Maximum depth of binary tree

Given a binary tree, find its maximum depth. The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.

Note: Leaf nodes are nodes that have no child nodes.

Ideas:

  • Depth traversal records and compares the depth of each path, taking the maximum value
// Depth traversal, compare each path
var maxDepth = function(root) {
    if(! root)return 0;
    let maxDep = 0;
    const deep = function(root, n){
        if(root.val) n++;
        maxDep = Math.max(maxDep, n);
        if(root.left) deep(root.left, n);
        if(root.right) deep(root.right, n);
    }
    deep(root, 0);
    return maxDep;
};

Copy the code
  • Breadth traverses from top to bottom, recording the number of layers until there is no node of the next layer
// Width traversal, record each layer of the tree node
var maxDepth = function(root) {
    if(! root)return 0;
    let maxDep = 0;
    let queue = [root];
    while(queue.length){
        maxDep++;  / / layer
        let curQue = []; // Record the root node for the layer traversal
        while(queue.length){
            let node = queue.shift();
            if(node.left) curQue.push(node.left);
            if(node.right) curQue.push(node.right);
        }
        queue = curQue;  
    }
    return maxDep;
};
Copy the code

Symmetric binary tree

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

Ideas:

  • Recursively compare the left subtree of the left subtree and the right subtree of the right subtree & the right subtree of the left subtree and the left subtree of the right subtree
/ / recursion
var isSymmetric = function(root) {
    if (root === null) return true;
    const isMirror = function(left, right){
        if(left === null && right === null) return true;
        if(left === null || right === null) return false;
        return (left.val === right.val) && isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }
    return isMirror(root.left, root.right);
};
Copy the code
  • The node data of each layer is iterated and recorded. The node array after reverse is compared with the original array. If the node array is consistent, it indicates symmetry.

Note: Remember to handle the null case.

/ / iteration
var isSymmetric = function(root) {
    if (root == null) return true
    let queue = [root]
    while(queue.length){
        let curArr = [];
        let nextQue = [];
        while(queue.length){
            let node = queue.shift();
            if(node === null){
                curArr.push('null');
            } else{ curArr.push(node.val); nextQue.push(node.left); nextQue.push(node.right); }}if(Array.from(curArr).reverse().toString() ! == curArr.toString())return false;
        queue = nextQue;
    }
    return true;
};
Copy the code

Path to the combined

You are given the root node of the binary tree and an integer targetSum representing the targetSum. Determine if there is a path from the root node to the leaf node in the tree. The sum of all nodes in the path equals the target and targetSum.

A leaf node is a node that has no children.

var hasPathSum = function(root, targetSum) {
    if(root === null) return false;
    // Determine the pause condition - the path is finished, and the leaf node is ready
    if(root.val === targetSum && root.left == null && root.right == null) return true;  
    targetSum = targetSum - root.val;
    return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
};
Copy the code