Algorithm brush problem – binary tree

100 Same tree

Leetcode-cn.com/problems/sa…

The recursive method

/ * * *@param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}* /
var isSameTree = function(p, q) {
    if(p === null || q === null) {if(p === null && q === null)
            return true;
        else
            return false;
    }

    if(p.val ! == q.val)return false;
    
    let left = isSameTree(p.left,q.left);
    let right = isSameTree(p.right,q.right);
    if(left && right)
        return true;
    else
        return false;
};
Copy the code

BFS solution

/** * 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} p
 * @param {TreeNode} q
 * @return {boolean}* /
var isSameTree = function(p, q) {
   let queue1 = [p];
   let queue2 = [q];

   while(queue1.length){
       let node1 = queue1.shift();
       let node2 = queue2.shift();

       if(! node1 || ! node2){if(node1 ! == node2)return false;
            else
                continue;// Continue shift if both are empty
       }
       if(node1.val ! = node2.val)return false;
       queue1.push(node1.left);
       queue1.push(node1.right);
       queue2.push(node2.left);
       queue2.push(node2.right);
   }
   return true;
};
Copy the code

---

113 Total Paths

/** DFS * } */
/ * * *@param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}* /
var pathSum = function(root, targetSum) {
    let res = [];

    const dfs = (root,sum,temp) = >{
        if(! root)return;
        temp.push(root.val);
        sum += root.val;
        if(! root.left && ! root.right){if(sum === targetSum)
                res.push(temp.slice());// Deep copy array
        }
        if(root.left)
            dfs(root.left,sum,temp);
        if(root.right)
            dfs(root.right,sum,temp);

        temp.pop();/ / back
        return;
    }

    dfs(root,0[]);return res;
};

Copy the code

112 Sum of Paths

/** DFS(first version) records the value of each path and compares the sum to the leaf node */
/ * * *@param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}* /
var hasPathSum = function(root, targetSum) {
    
    let temp = [];
    let flag = false;

    function dfs(root){
        if(! root)// If it is null
            return;
        temp.push(root.val);/ / into the stack

        if(! root.left && ! root.right){let sum = temp.reduce((pre,cur) = >{return pre + cur})
            if(sum === targetSum)
                flag = true;
        }
        dfs(root.left);
        dfs(root.right);
        temp.pop();// back up the stack
    }
    dfs(root);

    return flag;
};
Copy the code

/** DFS changes targetsum */ for each layer
/ * * *@param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}* /
var hasPathSum = function(root, targetSum) {
    if(! root){return false;
    }
    if(! root.left && ! root.right){if(root.val === targetSum)
            return true;
        else
            return false;
    }
    
    let left = hasPathSum(root.left, targetSum - root.val);
    if(left) return true;
    let right = hasPathSum(root.right, targetSum - root.val);
    if(right) return true;
    return false;
};
Copy the code

257 All paths to the binary tree

/** DFS */
/ * * *@param {TreeNode} root
 * @return {string[]}* /
var binaryTreePaths = function(root) {
    if(! root)return [];
    let res = [];

    function dfs(root,str){
        let oldStr = str;// Record the original value for backtracking
        if(! root)return;
        if(! root.left && ! root.right){// the leaf node is only concatenated
            str += root.val;
            res.push(str);
            return;
        }
        let temp = root.val +'- >';// Add an intermediate node ->
        str += temp;

        dfs(root.left,str);
        dfs(root.right,str);
        str = oldStr;/ / back
        return;     
    }
    dfs(root,"")
    return res;

};
Copy the code

129 Find the sum of the numbers from the root to the leaf

/** DFS */
/ * * *@param {TreeNode} root
 * @return {number}* /
var sumNumbers = function(root) {
    if(! root)return 0;
    let res = [];
     function dfs(root,str){
        if(! root)return;
        let oldStr = str;
        str += String(root.val);
        if(! root.left && ! root.right){ res.push(Number(str));
            return;
        }

        dfs(root.left,str);
        dfs(root.right,str);

        str = oldStr;
        return;
     }
     dfs(root,"");
     return res.reduce((total,cur) = >{return total + cur});
    
};
Copy the code

437 Sum of paths (not necessarily root to leaf) ***

Leetcode-cn.com/problems/pa…

/** DFS + recursive */
/ * * *@param {TreeNode} root
 * @param {number} sum
 * @return {number}* /
var pathSum = function(root, sum) {
    if(! root)return 0;
    function dfs(root,tempSum){
        if(! root)return 0;
        tempSum += root.val;

        let l = dfs(root.left,tempSum);
        let r = dfs(root.right,tempSum);
        // Add one if there is a valid path to the node
        return l + r + (tempSum === sum ? 1 : 0);
    }
    // Number of entries starting from the root number of entries starting from the left subtree Number of entries starting from the right subtree
    return dfs(root,0) + pathSum(root.left,sum) + pathSum(root.right,sum);

};
Copy the code

---

102 Hierarchical traversal of binary trees

Leetcode-cn.com/problems/bi…

/** BFS */
/ * * *@param {TreeNode} root
 * @return {number[][]}* /
var levelOrder = function(root) {
    let res = [];
    if(! root)return res;
    let queue = [root];
    while(queue.length){
        let length = queue.length;
        let temp = [];
        while(length--){
            let top = queue.shift();
            temp.push(top.val);
            if(top.left){
                queue.push(top.left);
            }
            if(top.right){
                queue.push(top.right);
            }
        }
        res.push(temp);
    }
    return res;
};
Copy the code

/** Dfs */
/ * * *@param {TreeNode} root
 * @return {number[][]}* /
var levelOrder = function(root) {
    let res = [];
    const dfs = (root,level) = >{
        if(! root)return;
            
        if(! res[level]) res.push([]); res[level].push(root.val); dfs(root.left,level +1);
        dfs(root.right,level + 1);
    }
    dfs(root,0);
    return res;
};
Copy the code

---

144 Anteorder traversal of binary trees

Leetcode-cn.com/problems/bi…

/**
 DFS
/**
 * @param {TreeNode} root
 * @return {number[]}* /
var preorderTraversal = function(root) {
    let res = [];

    let dfs = (root) = >{
        if(! root)return;
        res.push(root.val);
        dfs(root.left);
        dfs(root.right);
        return;
    }
    
    dfs(root);
    return res;
};
Copy the code

/** DFS iteration */
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var preorderTraversal = function(root) {
    
    let res = [];
    if(! root)return res;
    let stack = [root];
    while(stack.length){
        let len = stack.length;
        while(len--){
            let now = stack.pop();
            res.push(now.val);
            if(now.right) stack.push(now.right);
            if(now.left) stack.push(now.left);// In order to give the left node on the stack, so the back of the stack}}return res;
};
Copy the code

199 Right view of the binary tree

/** BFS */
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var rightSideView = function(root) {
    let res = [];
    if(! root)return res;
    let queue = [root];
    while(queue.length){
        let len = queue.length;
        let temp = [];
        let top;
        while(len--){
            top = queue.shift();
            if(top.left) queue.push(top.left);
            if(top.right) queue.push(top.right);
        }
        res.push(top.val);
    }
    return res;
};
Copy the code

104 Maximum depth of a binary tree

Leetcode-cn.com/problems/ma…

/** DFS recursive */
/ * * *@param {TreeNode} root
 * @return {number}* /
var maxDepth = function(root) {
    let max = 0;
    let dfs = (root,level) = >{
        if(! root)return;
        if(! root.left && ! root.right){ max = max > level ? max : level; } dfs(root.left,level +1);
        dfs(root.right,level + 1);
        return;
    }
    dfs(root,1);
    return max;
};
Copy the code

/** bfs */
/ * * *@param {TreeNode} root
 * @return {number}* /
var maxDepth = function(root) {
    if(! root)return 0;
    let queue = [root];
    let level = 0;
    while(queue.length){
        level++;
        let len = queue.length;
        while(len--){
            let top = queue.shift();
            if(top.left) queue.push(top.left);
            if(top.right) queue.push(top.right); }}return level;
};
Copy the code

111 Minimum depth of a binary tree

/** DFS recursive */
/ * * *@param {TreeNode} root
 * @return {number}* /
var minDepth = function(root) {
    let min = Infinity;
    if(! root)return 0;
    let dfs = (root,level) = >{
        if(! root)return;
        if(! root.left && ! root.right){ min =Math.min(min,level);
            return;
        }
        dfs(root.left,level+1);
        dfs(root.right,level+1);
        return;
    }
    dfs(root,1);
    return min;
};
Copy the code

/** bfs */
/ * * *@param {TreeNode} root
 * @return {number}* /
var minDepth = function(root) {
    if(! root)return 0;
    let queue = [root];
    let depth = 0;
    while(queue.length){
        depth++;
        let len = queue.length;
        while(len--){
            let node = queue.shift();
            let left = node.left;
            let right = node.right;
            if(! left && ! right)return depth;// Hierarchy traversal returns a leaf node without traversing the entire tree
            if(left)
                queue.push(left);
            if(right) queue.push(right); }}return depth;

};
Copy the code

101 symmetric binary trees

Leetcode-cn.com/problems/sy…

/ * * recursion * /
/ * * *@param {TreeNode} root
 * @return {boolean}* /
var isSymmetric = function(root) {
    if(! root)return true;
    // a recursive function
    function isSame(root1,root2){
        if(! root1 && ! root2)// Both are null
            return true;
        if(! root1 || ! root2 || root1.val! == root2.val)// One is null or has different values
            return false;
        let a = isSame(root1.left,root2.right);// Determine whether the left side of the left subtree is the same as the right side of the right subtree
        let b = isSame(root1.right,root2.left);// Determine whether the right side of the left subtree is the same as the left side of the right subtree
        if(a && b)
            return true;
        return false;
    }
    return isSame(root.left,root.right);
};
Copy the code

/** BFS */
/ * * *@param {TreeNode} root
 * @return {boolean}* /
var isSymmetric = function(root) {
    if(! root)return true;
    let queue = [root];

    while(queue.length){
        let len = queue.length;
        let temp = [];
        while(len--){
            let node = queue.shift();
            if(! node) temp.push(null);
            else{ temp.push(node.val); queue.push(node.left); queue.push(node.right); }}// Double pointer method to check whether palindrome array
        let left = 0;
        let right = temp.length - 1;
        while(left <= right){
            if(temp[left]! ==temp[right])return false; left++; right--; }}return true;
 
};
Copy the code

110 balanced binary tree

Leetcode-cn.com/problems/ba…

/** DFS recursive /** *@param {TreeNode} root
 * @return {boolean}* /
var isBalanced = function(root) {
    let flag = true;

    function height(root){// This function can get the height of the tree
        if(! root)return 0;
        let left = height(root.left);
        let right = height(root.right);
        
        if(Math.abs(left - right) > 1)// If not, flag=false
            flag = false;
        return Math.max(left,right) + 1;
    }

    height(root);
    return flag;
};
Copy the code

404 Sum of left leaves

Leetcode-cn.com/problems/su…

/** DFS */
/ * * *@param {TreeNode} root
 * @return {number}* /
var sumOfLeftLeaves = function(root,isLeft = false) {
    if(! root)return 0;
    if(! root.left && ! root.right && isLeft){return root.val;
    }
    return sumOfLeftLeaves(root.left,true) + sumOfLeftLeaves(root.right,false);
};
Copy the code

The most recent common ancestor of 236 binary trees ***

/** DFS */
/ * * *@param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}* /
var lowestCommonAncestor = function(root, p, q) {
    if(! root)return null;
    if(root === p || root === q)
        return root;
    let l = lowestCommonAncestor(root.left,p,q);// Is there p q in the left subtree
    let r = lowestCommonAncestor(root.right,p,q);
	// At least one must not be Null
    if(l && r)
        return root;
    if(! l)return r;
    return l;
        
};
Copy the code

Convert an ordered array to a binary search 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 {number[]} nums
 * @return {TreeNode}* /

var sortedArrayToBST = function(nums) {
    if(nums.length === 0)
        return null;

    let left = 0;
    let right = nums.length;
    let mid = (left + right) >> 1;
    
    let root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums.slice(left,mid));
    root.right = sortedArrayToBST(nums.slice(mid + 1, right));

    return root;
    
    
};
Copy the code

450 Delete a node in the binary search tree

Leetcode-cn.com/problems/de…

/** * 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 null;
    if(root.val ! == key){if(root.val > key)
            root.left = deleteNode(root.left, key);
        else
            root.right = deleteNode(root.right, key);
        return root;
    }
    // This node is the node to be deleted

    // The leaf node returns directly
    if(! root.left && ! root.right)return null;
    // There is only one subtree
    if(! root.left)return root.right;
    if(! root.right)return root.left;

    If there are two subtrees, join the right node to the rightmost node of the left subtree and return the left subtree
    let leftNode = root.left;
    while(leftNode.right){
        leftNode = leftNode.right;
    }
    leftNode.right = root.right;
    return root.left;
};
Copy the code