代码随想录算法训练营第十七天｜110-257-404

LeetCode 110. 平衡二叉树

思路并不复杂，如果当前节点是平衡的，那么判断子节点是否平衡

class Solution {
    public boolean isBalanced(TreeNode root) {

        if (root == null) {
            return true;
        }

        if (Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1) {
            return isBalanced(root.left) && isBalanced(root.right);
        }else {
            return false;
        }
    }

    private int getHeight (TreeNode root) {
        if (root == null) {
            return -1;
        }
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }
}

LeetCode 257.二叉树的所有路径

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ans = new LinkedList();
        
        if (root != null) {
            traversal(root, new LinkedList<Integer>(), ans);
        }

        return ans;
    }

    private void traversal (TreeNode node, List<Integer> path, List<String> ans) {
        
        // add the value of this node
        path.add(node.val);

        // if this node is a leaf node, convert the Integer list to String
        // and record it in ans
        if (node.left == null && node.right == null) {

            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < path.size() - 1; i++) {
                sb.append(String.valueOf(path.get(i)));
                sb.append("->");
            }

            sb.append(path.get(path.size() - 1));
            ans.add(new String(sb));

            return;
        }

        // if there is child node, recursively call this func
        if (node.left != null) {
            traversal(node.left, path, ans);
            // note here, we need to BACKTRACK the path list after we checked this path
            path.remove(path.size() - 1);
        }

        if (node.right != null) {
            traversal(node.right, path, ans);
            path.remove(path.size() - 1);
        }
    }
}

LeetCode 404.左叶子之和

递归的核心步骤，确定递归传入参数，递归出口，单层处理逻辑，over.

class Solution {

    public int sumOfLeftLeaves(TreeNode root) {
        
        // null node is invalid
        if (root == null) return 0;
        // leaf node has no child node anymore
        if (root.left == null && root.right == null) return 0;

        // for every node, deal with its left, right and itself

        // left node
        int leftValue = 0;
        // if left child node is a leaf node
        if (root.left != null && root.left.left == null && root.left.right == null) {
             leftValue = root.left.val;
        }else {
            leftValue = sumOfLeftLeaves (root.left);
        }

        // right node
        int rightValue =  sumOfLeftLeaves(root.right);

        //itself
        return leftValue + rightValue;
    }

}