代码随想录day17【二叉树】平衡二叉树 二叉树的所有路径 左叶子之和

平衡二叉树

力扣题目
思路：

1. 首先确定为后序遍历（求高度相关）
2. 递归三部曲

var isBalanced = function(root) {
    var getHeight = function(node){
        if(!node) return 0

        let leftHeight = getHeight(node.left)
        let rightHeight = getHeight(node.right)
        if(leftHeight === -1) return -1
        if(rightHeight === -1) return -1

        if(Math.abs(leftHeight-rightHeight) >1) return -1
        return 1+Math.max(leftHeight,rightHeight) //// 以当前节点为根节点的树的最大高度
    }
    return getHeight(root) !== -1
};

二叉树的所有路径

力扣题目
思路：

image.png

var binaryTreePaths = function(root) {
    let path=[]
  let res =[]

  let travel=function(node){
    path.push(node.val)
    if(!node.left && !node.right){
      res.push(path.join('->'))
      return
    }

    if(node.left){
        travel(node.left)
        path.pop()
    }
    if(node.right) {
        travel(node.right)
        path.pop()

    }
  }

  travel(root,path)
  return res
};

左叶子之和

注意：左叶子的定义

image.png

关键问题：如何判断终止条件。若与前文的判断条件一致，只能判断是否为叶子结点，而不能判断为左叶子结点
力扣题目链接
思路：
递归到倒数第二层的结点。收集其后代的左叶子结点的值。