代码随想录训练营Day17 | 110.平衡二叉树, 257.二

110. 平衡二叉树

思路

• 平衡二叉树定义：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
• 分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。
• 如果最终结果返回 -1，则不是一个平衡二叉树。

var isBalanced = function(root) {
    const getDepth = (root) => {
        if (!root) {
            return 0
        }
        let leftDepth = getDepth(root.left)
        if (leftDepth === -1) {
            return -1
        }
        let rightDepth = getDepth(root.right)
        if (rightDepth === -1) {
            return -1
        }
        if (Math.abs(leftDepth - rightDepth) > 1) {
            return -1
        } else {
            return 1 + Math.max(leftDepth, rightDepth)
        }
    }
    return !(getDepth(root) === -1)
};

257. 二叉树的所有路径

思路

var binaryTreePaths = function(root) {
    let res = []
    const getPath = (node, curPath) => {
        if (!node.left && !node.right) {
            curPath += node.val
            res.push(curPath)
            return
        }
        curPath += node.val + "->"
        node.left && getPath(node.left, curPath)
        node.right && getPath(node.right, curPath)
    }
    getPath(root, "");
    return res
};

404. 左叶子之和

思路

• 关于左叶子定义：如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子。
• 计算左叶子满足条件： if (root.left && !root.left.left && !root.left.right) { }

var sumOfLeftLeaves = function(root) {
    let res = 0
    const getLeaves = (root) => {
        if (!root) {
            return
        }
        if (root.left && !root.left.left && !root.left.right) {
            res += root.left.val
        }
        getLeaves(root.left)
        getLeaves(root.right)
    }
    getLeaves(root)
    return res
};