#LeetCode# Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

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

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

此题是上一道题的小变形，我们直接将上一道题的结果倒序整理一次即可。

可是实际操作中，遇到了新的问题，

定义一个新的reverseResult动态数组，ArrayList<ArrayList<Integer>> reverseResult = new ArrayList<ArrayList<Integer>> ();
运行，出现如下错误，

Line 44: error: no suitable method found for add(List<Integer>)

分析一下。

之前的result是 ArrayList<List<Integer>> result = new ArrayList<List<Integer>> ();

我们想将result中的结果用.add()方法加入到reverseResult中去，却提示没有相应的add(List<Integer>)方法。

仔细比较一下result和reverseResult，可以发现，我们的定义中，result是存储List的动态数组(虽然我们实际加入的nodeValues是ArrayList)，而reverseResult是存储数组的动态数组。

前者的List<Integer>无法直接add进入后者的ArrayList<Integer>中，而ArrayList是可以加入到List中。

所以，我们需要修改reverseResult的定义，为 ArrayList<List<Integer>> reverseResult = new ArrayList<List<Integer>> ()，in this way，我们的编译通过了！这里依旧是List和ArrayList的问题。


好了，戴上套套，上代码吧，

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>> ();
        List<Integer> nodeValues = new ArrayList<Integer> ();
        ArrayList<List<Integer>> reverseResult = new ArrayList<List<Integer>> ();
        
        if(root == null) {
            return result;
        }
        
        LinkedList<TreeNode> current = new LinkedList<TreeNode> ();
        LinkedList<TreeNode> next = new LinkedList<TreeNode> ();
        current.add(root);
        
        while(!current.isEmpty()) {
            TreeNode node = current.remove();
            nodeValues.add(node.val);
            
            if(node.left != null) {
                next.add(node.left);
            }
            if(node.right != null) {
                next.add(node.right);
            }
            
            if(current.isEmpty()) {
                result.add(nodeValues);
                current = next;
                next = new LinkedList();
                nodeValues = new ArrayList();
            }
        }
        
        for (int i = result.size() - 1; i >= 0; i--) {
            reverseResult.add(result.get(i));
        }
        
        return reverseResult;
        
    }

}

~~这周要把BFS刷掉！

#LeetCode# Binary Tree Level Order Traversal

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]
]

这是一道很简单的BFS题，思路看一下题目立刻就有了，但是编码的过程中遇到了不少问题。

给定一个树，按照层续遍历，输出每一层的节点。当然要用队列来实现了！值得注意的是，怎么控制层数呢？

巧妙地引入两个list，current和next，分别代表当前层和下一层，当current当前层遍历完毕后，current<--next，再将next层重新定义。当然，只用一个list也可以实现，我的思路是每次将当前层数和node都加入队列。

实现起来的时候，我遇到了好几个问题，

1. Incompatible types List of List and ArrayList of ArrayList
2. Type mismatch: cannot convert from ArrayList to List
3.  ArrayList<ArrayList<Integer>> cannot be converted to List<List<Integer>>
4. input[1] expected [[1]]，我的代码却output []，发现忘了加“!”， while(!current.isEmpty())

最终借助stackoverflow都解决了，这是一个疑难点，我会专门写文章归纳，这里简单用代码归纳下，就是，

        List<List<Integer>> result = new ArrayList<List<Integer>> ();
        ArrayList<Integer> nodeValues = new ArrayList<Integer> ();
        result.add(nodeValues);

好了，上代码吧，DEBUG了一个小时的代码.....

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        
        List<List<Integer>> result = new ArrayList<List<Integer>> ();
        ArrayList<Integer> nodeValues = new ArrayList<Integer> ();
        
        if(root == null) {
            return result;
        }
        
        LinkedList<TreeNode> current = new LinkedList<TreeNode>();
        LinkedList<TreeNode> next = new LinkedList<TreeNode>();
        current.add(root);
        
        while(!current.isEmpty()) {
            TreeNode node = current.remove();
            nodeValues.add(node.val);
            
            if(node.left != null) {
                next.add(node.left);
            }
            if(node.right !=null) {
                next.add(node.right);
            }
            
            if(current.isEmpty()) {
            current = next;
            next = new LinkedList<TreeNode> ();
            result.add(nodeValues);
            nodeValues = new ArrayList ();
            }
        }
        
        return result;
}
}





********************分割线，错误代码********************

//这段代码就是刚开始错误重重不能通过的代码，放在这里以供日后比较。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>> ();//错误
        ArrayList<Integer> nodeValues = new ArrayList<Integer> ();  //错误
        
        if(root == null) {
            return result;
        }
        
        LinkedList<TreeNode> current = new LinkedList<TreeNode>();
        LinkedList<TreeNode> next = new LinkedList<TreeNode>();
        current.add(root);
        
        while(current.isEmpty()) {   //应该为不为空的时候
            TreeNode node = current.remove();
            
            if(node.left != null) {
                next.add(node.left);
            }
            if(node.right !=null) {
                next.add(node.right);
            }
            
            nodeValues.add(node.val);
            
            if(current.isEmpty()) {
            result.add(nodeValues);
            current = next;
            next = new LikedList<TreeNode> ();
            nodeValues = new ArrayList<Integer> ();
            }
        }
        
        return result;
}
}

#LeetCode# Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

这道题值得反复回味，两种解法，一种迭代，一种递归。

迭代解法，层序遍历，

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public List<Integer> rightSideView(TreeNode root) {

        List<Integer> ret = new ArrayList<Integer>();

        if(root == null) return ret;

        Queue<TreeNode> q = new LinkedList<TreeNode>();

        q.offer(root);

        while(!q.isEmpty()) {

            int cnt = q.size();

            for(int i = 0; i < cnt; i++) {

                TreeNode cur = q.poll();

                if(i == cnt-1) {

                    ret.add(cur.val);

                }

                if(cur.left != null) {

                    q.offer(cur.left);

                }

                if(cur.right != null) {

                    q.offer(cur.right);

                }

            }

        }

        return ret;

    }

}

递归解法，

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public List<Integer> rightSideView(TreeNode root) {

        List<Integer> ret = new ArrayList<Integer>();

        if(root == null) return ret;

        int level = 1;

        helper(root, level, ret);

        return ret;

        

    }

    

    public void helper(TreeNode root, int level, List<Integer> ret) {

        if(root == null) 

            return;

        if(level > ret.size()) {

            ret.add(root.val);

        }

        

        helper(root.right, level + 1, ret);

        helper(root.left, level + 1, ret);

        

    }

}

这里注意，递归调用helper的次序，先遍历root.right，再遍历root.left。巧妙地运用level来控制ret取到每一层的最右结点权值，妙不可言呢！

#LeetCode# Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

这道题让我疑惑了半个上午，现在还是似懂非懂的状态，那就写下来捋一捋思路吧。

需要用到前度遍历，自父节点起先处理左孩子，再处理右孩子。左孩子链接到root.right，右孩子链接到root.right.right。递归即可。先是这样写了一下，然后出现Overflow错误，问题出现在哪儿呢？我的传递进去的参数是TreeNode root，然后递归中的处理一直都是基于root，相当于对root反复进行操作，并没有如愿DFS。怎么办！

再引入一个变量，lastNode，来记录每一层要处理的节点。然后基于lastNode来处理。

上代码，

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    private TreeNode lastNode = null;
    
    public void flatten(TreeNode root) {
        if(root == null) 
            return ;
        if(lastNode != null) {
            lastNode.left = null;
            lastNode.right = root;
        }
        
        lastNode = root;
        TreeNode right = root.right;
        flatten(root.left);
        flatten(right);
        
    }

}

我们初始定义lastNode为null，进入递归，赋予root；对lastNode进行处理，相当于对root处理，左孩子置为null，右孩子置为root，相当于第一层；然后分别遍历左右孩子树。

明天需要再回顾一下这道题。

#LeetCode# Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

这道题很简单，递归无脑。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        
        if(root == null) 
            return 0;
        if(root.left == null) 
            return minDepth(root.right) + 1;
            
        if(root.right == null) 
            return minDepth(root.left) + 1;
        
        return Math.min(
            minDepth(root.right), minDepth(root.left)) + 1;
        
    }
}

#LeetCode# 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,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

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

这道题得逆向思维。

之前考虑的一直都是，怎么从根到叶子的结点权值挨个相加，然后与sum值比较。这样就得考虑叶子个数的数的处理，如何存储或者输出？用递归的话该如何实现？怎么分清楚左右子树。头大。

换个思路，将sum自根节点起逐步减结点权值，最后与叶子的权值比较，这样就好处理多了！！

核心代码就一句，return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);

上代码。

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public boolean hasPathSum(TreeNode root, int sum) {

        

        if(root == null)

            return false;

            

        if(root.val == sum && root.left == null && root.right == null)

            return true;

        

        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);

    }

}

#LeetCode# Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

对给定的数逐位求和，直至得到的结果是个位数。以前处理过逐位求和，无非是sum=sum+num%10, num=num/10。

这里我们加上判断结果是否为个位数的判定条件，然后递归调用即可。

上代码，

public class Solution {

    public int addDigits(int num) {

        num = sum(num);

        while(num > 9) {

            num = sum(num);

        }

        return num;

    }

    

    private int sum(int num) {

        int sum = 0;

        while (num >0) {

        sum = sum + num % 10;

        num = num/10;

        }

        return sum;

    }

}

此方法的时间复杂度是多少呢？

如何用O(1)求解，这是个问题。

#LeetCode# Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

去年用OCaml学算法的时候做过这题，清楚记得当初法语描述是mirror arbre。这次用java做，遇到几个问题，

1. 不仅要考虑左右两子树同时为Null的情况，还要考虑两者不同时为Null的情况
2. 镜面树，是严格对称。第一次写成了left.left==right.left && left.right==right.right 结果Fail我还纳闷了半天

好了，上代码，

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

}

平时的课好好学，还是很有用的。M1的目标就是好好学算法和数学。加油！

#LeetCode# Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

这个问题困扰了我快一个星期（小偷懒！）今天早晨拿出来重新看，仔细回味在某处看到的“先处理右子树”。有了灵光。

与上一个完全二叉树的问题比较，此树为任意树，意味着某个节点可能没有兄弟节点，或堂兄弟节点等，我们的难题在于怎么找到后继节点，怎么把当前节点与未知的XX节点链接起来。

所以，简化过程，

1. 先找到右孩子的第一个有效next链接节点

2. 左孩子nxet后继链接1中的有效next链接节点

这就是所谓的“先处理右子树”，相应的，我们的递归也先递归右子树。

上代码，

/**

 * Definition for binary tree with next pointer.

 * public class TreeLinkNode {

 *     int val;

 *     TreeLinkNode left, right, next;

 *     TreeLinkNode(int x) { val = x; }

 * }

 */

public class Solution {

    public void connect(TreeLinkNode root) {

        if (root == null) {

            return;

        }

    //1.先找右孩子第一个有效的next链接节点

    TreeLinkNode p = root.next;

    TreeLinkNode Node = null;

    while (p != null) {

        if (p.left != null) {

            Node = p.left;

            break;

        }

        if (p.right != null) {

            Node = p.right;

            break;

        }

        p = p.next;

    }

    

    //2. 左孩子nxet后继链接1中的有效next链接节点

    if (root.right != null) {

        root.right.next = Node;

    }

    

    if (root.left != null) {

        if (root.right != null) {

            root.left.next = root.right;

        } else {

            root.left.next = Node;

        }

    }

    

    //3.递归调用

    connect(root.right);

    connect(root.left);

    

    }

}

这里用Node来代表右孩子第一个有效的next链接节点，while语句判断两种情况，左子树不为空和左子树空右子树不为空。

接下来的链接过程与完全二叉树情况类同，不表。递归，注意先递归右子树，因为我们需要先处理右孩子/树。

好了，有点绕脑子的问题就停滞下来，该加把劲儿了。

LOL! 

#LeetCode# Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

这道题目A的过程很是艰辛，历经数次超时，终于找到原因。先瞅瞅我这超时的代码吧。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        int length = nums.length;
        if (nums == null)  //或者length == 0
            return null; 
        return BuildBST(nums, 0, length-1);
    }
    
    public TreeNode BuildBST(int[] nums, int start, int end) {
        if (start > end) 
            return null;
        int mid = (start+end)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = BuildBST(nums, 0, mid-1);  //错误的地方，应修改为root.left = BuildBST(nums, start, mid-1);
        root.right = BuildBST(nums, mid+1, end);
        return root;
    }
}

原理依旧很简单，DFS，递归，只要找清楚mid，start和end，神马都好说。可是，我的问题依旧是Time Limit Exceeded。

Where is the problem? What the hell should I solve it!

仔细看代码，BuildBST方法出问题了，就在root.left那一行，参数传递错误，本应该传递start我却传递的是0.

修改之，root.left = BuildBST(nums, start, mid-1); 再次提交，Accepted.

再说说之前编码遇到的几个小问题，

1.判断nums为空，与判断nums.length为0是一个意思；
2.创建树，需要new一个TreeNode不够熟练；
3.定义方法的时候，一定注意参数的类型，像我刚开始就忘了定义start和end的类型了
4.最后返回的是root，就是我们的TreeNode.

#LeetCode# Populating Next Right Pointers in Each Node

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

题目有点长，populate是填入、构成的意思。题目大意是，对每一个节点用指针后继与其右边节点链接起来，如果节点右边没有节点，则指针后继为Null。题目假设给定的树为完全二叉树，给定常数额外空间。

可笑的喔，上来先看图，把题目理解成广度优先搜索挨个把节点值置换为Null，真是可笑。

思路马上就有了，对节点进行链表处理，left.next = right，这样的处理比单双向链表的删除插入还要简单。不过我们还是不能大意，

1.对于，题图中的2、3节点，由于是同一个节点的左右孩子节点，root.left.next = root.right即可

2.对于题目中5、6节点呢？5和6节点不在同一个节点上。我们用root2和root3分别表示2、3节点，root2.left.next = root3.left可以处理。可是，root2和root3该如何表示呢？不要忘了，在上一层，这个时候的3节点已经是2节点的后继节点了，所以我们有root2.right.next = root.next.left。

具体处理的逻辑已经确定，我们下一步需要确定的是条件语句，核心判断节点是否为Null。直接上代码，

/**

 * Definition for binary tree with next pointer.

 * public class TreeLinkNode {

 *     int val;

 *     TreeLinkNode left, right, next;

 *     TreeLinkNode(int x) { val = x; }

 * }

 */

public class Solution {

    public void connect(TreeLinkNode root) {

        if (root == null) 

            return;

        if (root.left != null) {  //父节点非空的情况，如2和3

            root.left.next = root.right;

        }

        if (root.right != null && root.next != null) { //不是兄弟节点的情况，如5和6

            root.right.next = root.next.left;

        }

        

        connect(root.left);

        connect(root.right);

        

    }

}

OK！洗漱滚上床去。

#LeetCode# Same Tree

开学前这阵真是无聊透顶，安卓的项目接近尾声，今天交大校友会的一师兄问我对新项目APP有没有兴趣，回答当然是好呀好呀有呀。今晚，来学习学习LeetCode吧。

经典“相似树”问题，这里注意有节点权值相等。思路很简单，首先判断根节点权值是否相等，然后递归左右子树，直接上代码了。

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public boolean isSameTree(TreeNode p, TreeNode q) {

        if (p == null && q == null) {

            return true;

        } else if (p == null || q==null) {

            return false;

        }

        if (p.val == q.val) {

                return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

            } else {

                return false;

            }

    }

}

提交了三次才Accepted，说说我遇到的问题，

1. 首先判断树为空的条件，两个空树也是相似树！！两个空树也是相似树！！并且注意是两个树同时为空！！一个为空，另一个不为空就是false；

  我们可以用笨办法，对四种情形挨个条件语句判断（别问我什么是四个..）

2.习惯性的return 0，LeetCode不接受，说是不支持int类型的boolean，只好乖乖改成false和true；

3.我有一个疑问，先判断p.val == q.val然后else，与先判断p.val !=q.val然后else，两种方法的效率是怎样的差别？

4.我还有一个疑问，每次编辑Blog总记不清楚自己用的是小号字还是正常大小的字，莫怪...

5.再补充一句，这次写的括号有点多...看起来怎么都不自然

LOL！

#LeetCode# 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.

自从来法国接触了OCaml，对递归从本能地抵触到现在本能地依赖...以前抵触是因为在国内刚讲C语言，老师就说递归不好效率低一般我们要避免使用，然后一个学期的OCaml课老师对于递归的洗脑，让我也变成了又懒又笨的依赖递归的人了。废话不多说，上代码。

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public int maxDepth(TreeNode root) {

        if (root == null)

            return 0;

        return Math.max(maxDepth (root.left), maxDepth (root.right)) + 1 ;

    }

}

直接手写代码，不过三次才Accepted，说说遇到的问题吧。

1.顾着高兴，直接return  (maxDepth (root.left), maxDepth (root.right)) + 1

2.root==null，刚开始二逼写成val=null...

3.第一次用Java的max，以为也是max(int, int)，谁知是Math.max(int, int)

一会儿吃完长棍，有心情了再写非递归的吧

LOL

再来完成下非递归的代码。

先说下思路，递归我们考虑的是DFS-深度优先，不使用递归的话，可以考虑BFS-广度优先。即层序遍历，遍历到最后一层（叶子）就是树的深度，这个时候再选择最大值即可。


public int maxDepth(TreeNode root) {
    if(root == null)
        return 0;
    int level = 0;
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    int curNum = 1; //当前层剩余的节点数目
    int nextNum = 0; //下一层的节点数目
    while(!queue.isEmpty())
    {
        TreeNode n = queue.poll();
        curNum--;
        if(n.left!=null)
        {
            queue.add(n.left);
            nextNum++;
        }
        if(n.right!=null)
        {
            queue.add(n.right);
            nextNum++;
        }
        if(curNum == 0)
        {
            curNum = nextNum;
            nextNum = 0;
            level++;
        }
    }
    return level;

}

这个不是太好理解，再来一个好理解的版本。

public class Solution {

    public int maxDepth(TreeNode root) {

        if(root == null)    return 0;

         

        // Non-recursive, use level order triversal

        ArrayList<TreeNode> q = new ArrayList<TreeNode>();

        q.add(root);

        int depth = 0;

         

        while(!q.isEmpty()) {

            ArrayList<TreeNode> next = new ArrayList<TreeNode>();

            for(TreeNode node : q) {

                if(node.left != null)   next.add(node.left);

                if(node.right != null)  next.add(node.right);

            }

            q = new ArrayList<TreeNode>(next);

            depth++;

        }

         

        return depth;

    }

}