Unit 1 Practice I

LeetCode 104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

• MaximumDepthofBinaryTree.jpg

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){val = x;}

    public static int maxDepth(TreeNode root){
        if (root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        int max = Math.max(left, right) + 1;
        return max;
    }

    public static void main (String args[]) {
        TreeNode binaryTree = new TreeNode(3);
        binaryTree.left = new TreeNode(4);
        binaryTree.right = new TreeNode(5);
        binaryTree.right.right = new TreeNode(6);
        maxDepth(binaryTree);
    }
}

Unit 2 Practice II

LeetCode 100. Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode (int x){val=x;}
}

public boolean isSameTree(TreeNode p, TreeNode q){
    if (p == null && q == null) { return true; }
    if (( p== null || q == null ) || ( p.val != q.val)) {
        return false;
    }
    return isSameTree (p.left, q.left) && isSameTree (p.right, q.right);
}

Unit 3 Practice III

LeetCode 112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

屏幕截图 2017-03-19 22.08.50.png

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

思路如下图：

• 屏幕截图 2017-03-20 21.02.44.png

//Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) {
        return false;
    }
    if(root.left == null && root.right == null && root.val == sum) {
        return true;
    }
    return hasPathSum (root.left, sum - root.val) || hasPathSum (root.right, sum - root.val);
    
}

Unit 4 Practice IV

LeetCode 257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

unspecified.jpg

All root-to-leaf paths are: ["1->2->5", "1->3"]

import java.util.*;

// Method: Divide and Conquer
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){val = x;}

    public static List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if(root == null) {
            return paths;
        }
        List<String> leftTreePaths = binaryTreePaths(root.left);
        List<String> rightTreePaths = binaryTreePaths(root.right);
        for(String path: leftTreePaths) {
            paths.add(root.val + "->" + path);
        }
        for(String path: rightTreePaths) {
            paths.add(root.val + "->" + path);
        }
        if(paths.size() == 0) {
            paths.add("" + root.val);
        }
        return paths;
    }

    public static void main (String args[]) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(7);
        List<String> paths = new ArrayList<>();
        paths = binaryTreePaths(root);
        for (String path: paths) {
            System.out.println(path);
        }
    }
}

Unit 5 Practice V

LeetCode 98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

屏幕截图 2017-03-20 21.55.08.png

思路：对二叉查找树（BST）进行中序遍历，可以得到一个递增的有序序列。如果不是递增的序列，说明不是Valid BST。

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){val = x;}

// Iterative
public boolean isValidBST(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode pre = null;
    while (!stack.isEmpty() || root != null) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        if (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (pre != null && pre.val >= cur.val){
                return false;
            }
            pre = cur;
            root = cur.right;
        }
    }
    return true;
}