LeetCode Day 13 Binary Tree Part 3

LeetCode No. 104. Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

LeetCode No. 257. Binary Tree Paths

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        String str = "";
        pathRecord(root,str,list);
        return list;
    }

    public void pathRecord(TreeNode cur, String str, List<String> result){
        str += cur.val;
        if(cur.left==null && cur.right == null){
            result.add(str);
        }else if(cur.left !=null && cur.right!=null){
            pathRecord(cur.left, str+"->", result);
            pathRecord(cur.right, str+"->", result);
        }
        else if(cur.left != null){
            pathRecord(cur.left, str+"->", result);
        }
        else{
            pathRecord(cur.right, str+"->", result);
        }


    }

LeetCode No. 222. Count Complete Tree Nodes

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 6

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        return 1+countNodes(root.left)+countNodes(root.right);
    }

LeetCode 404. Sum of Left Leaves

Given the root of a binary tree, return the sum of all left leaves.

A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.

Example 2:

Input: root = [1]
Output: 0

Constraints:

The number of nodes in the tree is in the range [1, 1000].
-1000 <= Node.val <= 1000

Original Page

    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        return leftLeaves(root, false);

    }

    public int leftLeaves(TreeNode cur, boolean isLeft){
        if(cur == null){
            return 0;
        }
        if(cur.left == null && cur.right == null && isLeft){
            return cur.val;
        }
        return leftLeaves(cur.left, true) + leftLeaves(cur.right, false);
    }