Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

1. One Queue Solution — Better

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
    //one queue
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    if (root != null) {
        q.offer(root);
    }
    while (!q.isEmpty()) {
        ArrayList<Integer> levelNodes = new ArrayList<>();
        int size = q.size(); //this is the # of nodes in current level
        for (int i = 0; i < size; i++) {
            TreeNode curr = q.poll();
            levelNodes.add(curr.val);
            if (curr.left != null) {
                q.offer(curr.left);
            }
            if (curr.right != null) {
                q.offer(curr.right);
            }
        }
        result.add(levelNodes);
    }
    return result;
}

2. Two Queues Solution — Easier to Understand

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> output= new ArrayList<ArrayList<Integer>>();
        if(root==null){
            return output;
        }
        ArrayList<TreeNode> current = new ArrayList<TreeNode>();
        ArrayList<TreeNode> children = new ArrayList<TreeNode>();
        current.add(root);
        while(current.size()!=0){
            children = new ArrayList<TreeNode>();
            ArrayList<Integer> levelNodes= new ArrayList<Integer>();
            for(TreeNode t : current){
                levelNodes.add(t.val);
                if(t.left!=null){
                    children.add(t.left);
                }
                if(t.right!=null){
                    children.add(t.right);
                }
            }
            output.add(levelNodes);
            current = children;
        }
        return output;
    }

Share

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.

  public boolean isValidBST(TreeNode root) {
      // write your code here
      return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
  
  }
  //return if the root val is within the [min,max] range
  public boolean isValidBSTHelper(TreeNode root, int min, int max) {
      if (root == null) {
          return true;
      }
      if (min > root.val || root.val > max) {
          return false;
      }
      return isValidBSTHelper(root.left, min, root.val - 1) &&
             isValidBSTHelper(root.right, root.val + 1, max);
  }

九章详解

Share

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(inorder.length==0){
            return null;
        }
        
        //last element of postorder is the root
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        //find the root element in the inorder array
        //elements occur before it are in its left sub-tree
        //elements occur after it are in its right sub-tree
        int index = 0;
        for(int i=0;i<inorder.length;i++){
            if(inorder[i]==root.val){
                index = i;
                break;
            }
        }
        int[] leftInOrder = new int[index];
        int[] leftPostOrder = new int[index];
        int[] rightInOrder = new int[inorder.length-index-1];
        int[] rightPostOrder = new int[inorder.length-index-1];
        
        for(int i=0;i<inorder.length;i++){
            if(i<index){
                leftInOrder[i] = inorder[i]; 
            }
            if(i>index){
                rightInOrder[i-index-1] = inorder[i];
            }
        }
        
        for(int i=0;i<postorder.length-1;i++){
            if(i<index){
                leftPostOrder[i] = postorder[i];
            }else{
                rightPostOrder[i-index]=postorder[i]; 
            }
        }
        
        root.left = buildTree(leftInOrder,leftPostOrder);
        root.right = buildTree(rightInOrder,rightPostOrder);
        return root;
    }
}

Share

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

1. Recursive Version

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    //recursive version
    ArrayList<Integer> result = new ArrayList<>();
    traversalHelper(root, result);
    return result;
}

public void traversalHelper(TreeNode root, ArrayList<Integer> result) {
    if (root == null) {
        return;
    }
    traversalHelper(root.left, result);
    result.add(root.val);
    traversalHelper(root.right, result);
}

2. Non-recursive Version

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    //non-recursive version
    ArrayList<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.empty()) {
        TreeNode left = curr;
        while (left != null) {
            stack.push(left);
            left = left.left;
        }
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }
    return result;
}

Share