題目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,可以根據(jù)二叉樹的定義來求解書的最大深度
                      0, root == null
 maxDepth(root) =     1+max(maxDepth(root.left),maxDepth(root.right))
2,可以采用層次遍歷, 有多少層,就是二叉樹的深度
3,可以利用二叉樹后序非遞歸遍歷的性質(zhì),棧中保存的是當(dāng)前節(jié)點的所有祖先節(jié)點(他的這些節(jié)點都
是未訪問過的).
所以當(dāng)我們遇到葉子節(jié)點的時候,棧中保存的就是該葉子節(jié)點到根節(jié)點的所有節(jié)點,那么該葉子的深度
就是棧中元素的個數(shù)

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,利用后序遍歷棧中元素的性質(zhì)

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){
                    //葉子節(jié)點
                    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;
    }