一、LeetCode 110 平衡二叉树

题目链接: 110.平衡二叉树https://leetcode.cn/problems/balanced-binary-tree/

思路：设置深度计算函数，进行递归处理。

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        boolean left = isBalanced(root.left);
        boolean right = isBalanced(root.right);
        int length_left = depth(root.left);
        int length_right = depth(root.right);
        int flag = length_left - length_right;
        if(flag >= -1 && flag <= 1){
            //本层平衡且左右子树均平衡
            return true && left && right;
        }else{
            return false;
        }
    }
    //计算子树深度
    public int depth(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        return left>right ? left+1 : right+1;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

 二、LeetCode 257 二叉树的所有路径

题目链接：257.二叉树的所有路径https://leetcode.cn/problems/binary-tree-paths/description/

思路：递归+回溯。

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<Integer> path = new ArrayList<>();
        List<String> ans = new ArrayList<>();
        path(root,path,ans);
        return ans;
    }
    public void path(TreeNode root, List<Integer> path, List<String> ans){
        path.add(root.val); //中
        //若为叶子节点则输出该路径
        if(root.left == null && root.right == null){
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < path.size()-1; i++){
                sb.append(path.get(i)).append("->");
            }
            //加入叶子节点
            sb.append(root.val);
            ans.add(sb.toString());
        }
        //回溯处理
        if(root.left != null){
            path(root.left,path,ans);
            path.remove(path.size()-1);
        }
        if(root.right != null){
            path(root.right,path,ans);
            path.remove(path.size()-1);
        }
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

 三、LeetCode 404 左叶子之和

题目链接：404.左叶子之和https://leetcode.cn/problems/sum-of-left-leaves/

思路：后序递归遍历、左叶子节点处理。

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        //递归遍历 左右中
        int left = sumOfLeftLeaves(root.left);
        int right = sumOfLeftLeaves(root.right);
        int mid = 0;
        //遇到左叶子节点就记录数值，否则记为0
        if(root.left != null && root.left.left == null && root.left.right == null){
            mid = root.left.val;
        }
        return left + mid + right;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

 四、小结

        假期结束，开刷OVO