DAY17|110.平衡二叉树，257.二叉树的所有路径，404.左子路之和

110.平衡二叉树

文字讲解：平衡二叉树

视频讲解：平衡二叉树

状态：用递归+后序遍历的思想完成，一看就会，一写就废；

思路：

用递归+后序遍历的思想完成

代码：

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    public int getHeight(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        if (Math.abs(leftHeight-rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

257.二叉树的所有路径

文字讲解：二叉树的所有路径

视频讲解：代码随想录-二叉树的所有路径

状态：这题我知道用前序遍历，也猜到用递归，也知道在叶子节点时收集，但是不知道怎么去把收集的容器清零，太考研递归代码技巧了

思路：

1、这一题涉及涉及到回溯，我觉得最关键的是这句"queue.poll();"在收集结果之后，将元素poll掉；

代码：

class Solution {

    public List<String> binaryTreePaths(TreeNode root) {
        //使用前序遍历完成，先打印父节点
        LinkedList<Integer> tempQueue = new LinkedList<>();
        List<String> results = new ArrayList<>();
        printTreePaths(root, tempQueue, results);
        return results;
    }

    public void printTreePaths(TreeNode node, LinkedList<Integer> queue, List<String> results) {
        queue.push(node.val);
        if (node.left == null && node.right == null) {
            //收集
            results.add(transferPathStr(queue));
            return;
        }
        if (node.left != null) {
            printTreePaths(node.left, queue, results);
            queue.poll();
        }
        if (node.right != null) {
            printTreePaths(node.right, queue, results);
            queue.poll();
        }
    }

    public String transferPathStr(LinkedList<Integer> pathList) {
        StringBuilder sb = new StringBuilder();
        for (int i = pathList.size()-1; i >= 0; i--) {
            if (i == 0) {
                sb.append(String.valueOf(pathList.get(i)));
            } else {
                sb.append(String.valueOf(pathList.get(i))).append("->");
            }
        }
        return sb.toString();
    }

}

404.左叶子之和

文字讲解：二叉树的所有路径

视频讲解：代码随想录-左子路之和

状态：递归硬解了，没想太多

思路：

代码：

class Solution {

    Integer sum = 0;

    public int sumOfLeftLeaves(TreeNode root) {
        sumLeftVal(root);
        return sum;
    }

    public void sumLeftVal(TreeNode node) {
        if (node.left == null && node.right == null) {
            return;
        }
        if (node.left != null) {
            if (node.left.left == null && node.left.right == null) {
                sum+=node.left.val;
            }
            sumLeftVal(node.left);
        }
        if (node.right != null) {
            sumLeftVal(node.right);
        }
    }
}