代码随想录算法训练营第17天

 */
class Solution {
    public boolean is_balance;
    public boolean isBalanced(TreeNode root) {
        this.is_balance = true;
        invert(root);
        return this.is_balance;
    }
    // 1.返回当前节点的高度
    public int invert(TreeNode node) {
        // 2.结束条件
        if(node == null) return 0;
        // 3.递归逻辑
        int left_height = invert(node.left);
        int right_height = invert(node.right);
        if(Math.abs(left_height - right_height) > 1) {
            this.is_balance = false;
        }
        return Math.max(left_height, right_height) + 1;
    }
}

class Solution {
    public List<String> ans;
    public List<TreeNode> path;
    public List<String> binaryTreePaths(TreeNode root) {
        this.ans = new ArrayList<>();
        this.path = new ArrayList<>();
        if(root != null) invert(root);
        return ans;
    }
    // 1.返回值：无
    public void invert(TreeNode node) {
        // 2.结束条件：到达叶子
        if(node.left == null && node.right == null) {
            this.path.add(node);
            this.ans.add(path2str());
            this.path.remove(this.path.size() - 1);
            return;
        }
        // 3.递归逻辑
        this.path.add(node);
        if(node.left != null) invert(node.left);
        if(node.right != null) invert(node.right);
        this.path.remove(this.path.size() - 1); // 回溯
    }
    // 路径list转字符串
    public String path2str() {
        String str = new String();
        for(int i = 0; i < this.path.size(); i++) {
            if(i == 0) {
                str = str.concat("" + this.path.get(i).val);
            }
            else {
                str = str.concat("->" + this.path.get(i).val);
            }
        }
        return str;
    }
}

 */
class Solution {
    public int left_sum;
    public int sumOfLeftLeaves(TreeNode root) {
        this.left_sum = 0;
        if(root != null) invert(root, false);
        return this.left_sum;
    }
    // 1.返回值：无，用this.left_sum记录了
    // 调用时用is_left_cld告诉递归函数这个节点是不是从左孩子来的
    public void invert(TreeNode node, boolean is_left_cld) {
        // 2.结束条件：到叶子了
        if(node.left == null && node.right == null) {
            if(is_left_cld) this.left_sum += node.val;
            return;
        }
        // 3.递归逻辑
        if(node.left != null) invert(node.left, true);
        if(node.right != null) invert(node.right, false);
    }
}