104. Maximum Depth of Binary Tree

题目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.

分析

1,可以根据二叉树的定义来求解书的最大深度
                      0, root == null
 maxDepth(root) =     1+max(maxDepth(root.left),maxDepth(root.right))
2,可以采用层次遍历, 有多少层,就是二叉树的深度
3,可以利用二叉树后序非递归遍历的性质,栈中保存的是当前节点的所有祖先节点(他的这些节点都
是未访问过的).
所以当我们遇到叶子节点的时候,栈中保存的就是该叶子节点到根节点的所有节点,那么该叶子的深度
就是栈中元素的个数

1,递归

递归式
                     0, root == null
 maxDepth(root) =     1+max(maxDepth(root.left),maxDepth(root.right))

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

2,利用层次遍历

 public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        List<TreeNode> curLevelNodes = new ArrayList<TreeNode>();
        curLevelNodes.add(root);
        int level = 0;
        while(!curLevelNodes.isEmpty()){
            List<TreeNode> nextLevelNodes = new ArrayList<TreeNode>();
            for(TreeNode node : curLevelNodes){
                if(node.left != null){
                    nextLevelNodes.add(node.left);
                }
                
                if(node.right != null){
                    nextLevelNodes.add(node.right);
                }
            }
            level++;
            curLevelNodes = nextLevelNodes;
        }
        return level;
    }

3,利用后序遍历栈中元素的性质

public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        TreeNode tempNode = null;
        boolean visited = false;
        int height = 0;
        do{
            while(node != null ){
                stack.push(node);
                node = node.left;
            }
            
            tempNode = null;
            visited = true;
            while(!stack.empty() && visited){
                node = stack.peek();
                if(node.right == tempNode){
                    //叶子节点
                    if(node.left == null && node.right == null){
                        height = height > stack.size() ? height : stack.size();
                    }
                    tempNode = node;
                    stack.pop();
                }else{
                    node = node.right;
                    visited = false;
                }
            }
        }while(!stack.empty());
        return height;
    }