Day 17 | 110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和

Leetcode 110.平衡二叉树

题目：110.平衡二叉树

初始思路

可以根据104.二叉树的最大深度改一下，获取左右两边子树的深度，然后比较。

代码

// 递归
var isBalanced = function (root) {
    const getDepth = function (node) {
        // 递归终止条件
        if (!node) return 0
        let leftDepth = getDepth(node.left)
        // 当判定左子树不为平衡二叉树时,即可直接返回-1
        if (leftDepth === -1) return -1
        let rightDepth = getDepth(node.right)
        // 当判定右子树不为平衡二叉树时,即可直接返回-1
        if (rightDepth === -1) return -1
        let delta = Math.abs(leftDepth - rightDepth)
        if (delta > 1) {
            // 当前左子树右子树高度相差大于1就返回-1
            return -1
        } else {
            return 1 + Math.max(leftDepth, rightDepth)
        }
    }
    return !(getDepth(root) === -1)
};

// 获取当前节点的高度
var getHeight = function (curNode) {
    let queue = [];
    if (curNode !== null) queue.push(curNode); // 压入当前元素
    let depth = 0, res = 0;
    while (queue.length) {
        let node = queue[queue.length - 1]; // 取出栈顶
        if (node !== null) {
            queue.pop();
            queue.push(node);   // 中
            queue.push(null);
            depth++;
            node.right && queue.push(node.right);   // 右
            node.left && queue.push(node.left);     // 左
        } else {
            queue.pop();
            node = queue[queue.length - 1];
            queue.pop();
            depth--;
        }
        res = res > depth ? res : depth;
    }
    return res;
}
var isBalanced = function (root) {
    if (root === null) return true;
    let queue = [root];
    while (queue.length) {
        let node = queue[queue.length - 1]; // 取出栈顶
        queue.pop();    
        if (Math.abs(getHeight(node.left) - getHeight(node.right)) > 1) {
            return false;
        }
        node.right && queue.push(node.right);
        node.left && queue.push(node.left);
    }
    return true;
};

感想

1. 递归还是挺好理解的。迭代也是模拟的后序遍历。

Leetcode 257.二叉树的所有路径

题目：257.二叉树的所有路径 讲解：https://www.bilibili.com/video/BV1ZG411G7Dh

初始思路

深度优先搜索

代码

var binaryTreePaths = function (root) {
    let res = []
    //1. 确定递归函数 函数参数
    const getPath = function (node, curPath) {
        //2. 确定终止条件，到叶子节点就终止
        if (node.left == null && node.right == null) {
            // 如果遇到了叶子节点就把路径放到结果数组中
            curPath += node.val
            res.push(curPath)
            return
        }
        // 3. 确定单层递归逻辑
        // 如果没遇到叶子节点就把这个点加入curPath上
        curPath += node.val + '->'
        // 继续遍历左右子树
        if (node.left) {
            getPath(node.left, curPath)
        }
        if (node.right) {
            getPath(node.right, curPath)
        }
    }
    getPath(root, '')
    return res
};

var binaryTreePaths = function (root) {
    if (!root) return []
    const stack = [root], paths = [''], res = []
    while (stack.length) {
        const node = stack.pop()
        let path = paths.pop()
        if (node.left == null && node.right == null) {
            // 如果遇到了叶子节点就把路径放到结果数组中
            res.push(path + node.val)
            continue
        }
        // 如果没遇到叶子节点就把这个节点继续连上
        path += node.val + '->'
        if (node.right) {
            stack.push(node.right)
            paths.push(path)
        }
        if (node.left) {
            stack.push(node.left)
            paths.push(path)
        }
    }
    return res
}

感想

1. 过程
   
2. 这次的迭代还挺好理解的，有点像层序遍历（

Leetcode 404.左叶子之和

题目：404.左叶子之和

初始思路

感觉用层序遍历可以做出来

代码

var sumOfLeftLeaves = function (root) {
    const nodeSum = function (node) {
        // 终止条件
        if (!node) return 0
        let leftValue = nodeSum(node.left) // 左
        let rightValue = nodeSum(node.right) // 右
        // 单层递归逻辑
        let midValue = 0 // 中
        if (node.left != null && node.left.left == null && node.left.right == null){
            // 如果这个节点左节点存在，并且左节点没有左右节点，说明是我们需要的左叶子
            midValue = node.left.val
        }
        let sum = midValue + leftValue + rightValue
        return sum
    }
    return nodeSum(root)
};

var sumOfLeftLeaves = function (root) {
    if (!root) return null
    let queue = []
    let sum = 0
    queue.push(root)
    while (queue.length) {
        let node = queue.shift()
        if (node.left != null && node.left.left == null && node.left.right == null){
            sum +=node.left.val
        }
        if (node.left) {
            queue.push(node.left)
        }
        if (node.right) {
            queue.push(node.right)
        }
    }
    return sum
}

感想

1. 左叶子的明确定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点。
   
2. 判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
3. 迭代就是层序遍历，只是在遍历的模板上加了判断，然后累加。