平衡二叉树

110. 平衡二叉树 - 力扣（LeetCode）

判断平衡二叉树就是要比较左右子树的高度差，在计算节点的高度时，如果高度差大于1，那么将该结果返回给父节点

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }
    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        // 如果子节点不是平衡二叉树，那么返回给父节点
        if (leftHeight == -1 || rightHeight == -1) {
            return -1;
        }
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight,rightHeight) + 1;
    }
}

二叉树的所有路径

257. 二叉树的所有路径 - 力扣（LeetCode）
每次遍历到一个节点时，就将字符串更新，直到遍历到叶子节点为止，虽然代码简介，但是思路不好想

class Solution {
    // 作为一个属性
    List<String> result = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        deal(root, "");
        return result;
    }
    private void deal(TreeNode node, String s) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            result.add(new StringBuilder(s).append(node.val).toString());
            return;
        }
        String tmp = new StringBuilder(s).append(node.val).append("->").toString();
        deal(node.left, tmp);
        deal(node.right, tmp);
    }
}

左叶子之和

404. 左叶子之和 - 力扣（LeetCode）
本题要注意左叶子节点的定义，需要是叶子节点，并且是父节点的左节点，所以判断条件有3个

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftValue = sumOfLeftLeaves(root.left);
        int rightValue = sumOfLeftLeaves(root.right);
        int midValue = 0;
        // 根据叶子节点的父节点判断
        if (root.left != null && root.left.left == null && root.left.right == null) {
            midValue = root.left.val;
        }
        int sum = midValue + leftValue + rightValue;
        return sum;
    }
}