代码随想录Day17-Leetcode110.平衡二叉树，257. 二叉树的所有路径，404.左叶子之和

110.平衡二叉树

题目链接:https://leetcode.cn/problems/balanced-binary-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 {TreeNode} root
 * @return {boolean}
 */
 //一个显然但似乎不太高效的方法是: 通过递归获取左右子树高度,判断差; 然后递归判断左右结点;
//那么一个显然的改进就是后序遍历
var isBalanced = function(root) {
    let obj = {result:true}
    postOrder(root,obj)
    return obj.result
};

var postOrder = function(node,obj){
    if(node == null){
        return 0
    }
    let lHeight = postOrder(node.left,obj)
    let rHeight = postOrder(node.right,obj)
    if(Math.abs(lHeight-rHeight)>1){
        obj.result = false
    }
    return Math.max(lHeight,rHeight)+1
}

看了题解后,发现可以在不平衡时返回-1,不需要传一个类似全局的参数对象;

非递归暂时跳过

257. 二叉树的所有路径

回溯,已经比较熟练了;
但还是出现了:递归函数传参不全

/**
 * 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) {
    let path = [] //用来存储临时"路径"
    let result = []//存储结果
    backtrack(root,path,result)
    return result
};

var backtrack = function(node, path,result){
    path.push(node.val)
    if(node.left==null&&node.right==null){
        result.push(path.join('->'))//若为叶子结点,则为一个有效结果
    }else{
        if(node.left){
            backtrack(node.left,path,result)
        }
        if(node.right){
            backtrack(node.right,path,result)
        }
    }
    path.pop()//遍历完子树,回溯为原来状态
}

看了题解,非递归用的好像是bfs,暂时略过

404. 左叶子之和

求和类的方法用自底向上很方便,所以用后序

/**
 * 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}
 */
 //问题:我要如何知道一个叶子是左叶子;答:遍历时传入一个flag
//思路:更接近自底向上,所以用后序
var sumOfLeftLeaves = function(root) {
    return postOrder(root,false)
};

var postOrder = function(node,flag){
    let leftSum = 0  //左子树的"左和"
    let rightSum = 0 //右子树的"左和"
    if(!node.left&&!node.right){
        return flag?node.val:0//若为叶子结点,则根据flag返回值或0
    }else{
        if(node.left){
            leftSum = postOrder(node.left,true)
        }
        if(node.right){
            rightSum = postOrder(node.right,false)
        }
    }
    return leftSum+rightSum
}

看了题解,非递归还是层序遍历,暂时跳过