代码随想录算法训练营第第17天 | 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和

三道题都没想出来，还是要加强递归的练习
110.平衡二叉树 （优先掌握递归）

再一次涉及到，什么是高度，什么是深度，可以巩固一下。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0110.平衡二叉树.html

function getHeight(node) {
    if (node === null) return 0;
    let leftHeight = 0;
    let rightHeight = 0;
    leftHeight = getHeight(node.left);
    if (leftHeight === -1) {
        return -1
    }

    rightHeight = getHeight(node.right);
    if (rightHeight === -1) {
        return -1;
    }
    if (Math.abs(leftHeight - rightHeight)>1) {
        return -1;
    }
    return Math.max(leftHeight,rightHeight) + 1;
}

/**
 * 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) {
    let height = getHeight(root);
    if (height === -1) {
        return false;
    }
    return true;
};

257. 二叉树的所有路径 （优先掌握递归）

这是大家第一次接触到回溯的过程， 我在视频里重点讲解了 本题为什么要有回溯，已经回溯的过程。
如果对回溯 似懂非懂，没关系， 可以先有个印象。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0257.二叉树的所有路径.html

递归加回溯
function getAllPath(node, path, results) {
    path.push(node.val);
    if (node.left === null && node.right === null) {
        let sPath = '';
        for (let i=0;i<path.length-1; i++) {
            sPath += path[i];
            sPath += '->';
        }
        sPath += path[path.length - 1];
        results.push(sPath);
        return;
    }
    
    if (node.left) {
        getAllPath(node.left, path, results);
        path.pop();
    }
    if (node.right) {
        getAllPath(node.right, path, results);
        path.pop();
    }
    
}
/**
 * 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 {string[]}
 */
var binaryTreePaths = function(root) {
    const path = [];
    const results = [];
    getAllPath(root, path, results);
    return results;
};

404.左叶子之和 （优先掌握递归）

其实本题有点文字游戏，搞清楚什么是左叶子，剩下的就是二叉树的基本操作。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0404.左叶子之和.html

递归
/**
 * 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 sumOfLeftLeaves = function(root) {
    if (root == null) return 0;
    if (root.left === null && root.right === null) return 0;
    let leftTol = sumOfLeftLeaves(root.left);
    if (root.left && root.left.left === null && root.left.right === null) {
        leftTol = root.left.val;
    }
    leftTol += sumOfLeftLeaves(root.right);
    return leftTol;

};