平衡二叉树

题目链接

https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html

思路

递归判断左右子树深度，如果差值为>1即是不平衡的

    public boolean isBalanced(TreeNode root) {
    return getDepth(root) != -1;
}

private int getDepth(TreeNode node) {
    if(node == null) {
        return 0;
    }
    int leftHeight = getDepth(node.left);
    if(leftHeight == -1) {
        return -1;
    }
    int rightHeight = getDepth(node.right);
    if(rightHeight == -1) {
        return -1;
    }
    if(Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    }
    return Math.max(leftHeight, rightHeight) + 1;
}

二叉树所有路径

题目链接

https://programmercarl.com/0257.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%89%80%E6%9C%89%E8%B7%AF%E5%BE%84.html

思路

递归回溯，每一次递归记录当前遍历的节点路径，递归出来后需要回溯进入下一次递归

    public List<String> binaryTreePaths(TreeNode root) {
    List<String> list = new ArrayList();
    List<Integer> path = new ArrayList();
    visitPaths(root, path, list);
    return list;
}

private void visitPaths(TreeNode node, List<Integer> path, List<String> res) {
    path.add(node.val);
    if(node.left == null && node.right == null) {
        // 输出
        StringBuilder sb = new StringBuilder();// StringBuilder用来拼接字符串，速度更快
        for (int i = 0; i < path.size() - 1; i++) {
            sb.append(path.get(i)).append("->");
        }
        sb.append(path.get(path.size() - 1));// 记录最后一个节点
        res.add(sb.toString());// 收集一个路径
        return;
    }
    if(node.left != null) {
        visitPaths(node.left, path, res);
        path.remove(path.size() - 1);
    }
    if(node.right != null) {
        visitPaths(node.right, path, res);
                    path.remove(path.size() - 1);

    }
}

左叶子之和

题目链接

https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html

思路

理解左叶子定义，递归实现

    public int sumOfLeftLeaves(TreeNode root) {
    if(root == null) {
        return 0;
    }
    int val = 0;
    if(root.left != null && root.left.left == null && root.left.right == null) {
        val = root.left.val;
    }
    return val + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}