二叉树的最大深度-蒲公英云

二叉树的最大深度

题目描述
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

TreeNode

class TreeNode { 
    int val;
    public TreeNode(int val) { 
        this.val = val;
    }
    TreeNode left;
    TreeNode right;
}

思路1：递归

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

思路2：使用队列进行迭代

public int maxDepth(TreeNode root) { 
        //Pair 为jdk1.8新增的util类
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<Pair<TreeNode,Integer>>();
        int max =0;
        if(root != null) { 
            queue.add(new Pair<TreeNode, Integer>(root, 1));
        }
        while(!queue.isEmpty()) { 
            Pair<TreeNode, Integer> pair = queue.poll();
            TreeNode node = pair.getKey();
            int curDepth = pair.getValue();
            if(node != null) { 
                max = Math.max(max, curDepth);
                queue.add(new Pair<TreeNode, Integer>(node.left, curDepth + 1));
                queue.add(new Pair<TreeNode, Integer>(node.right, curDepth + 1));
            }
        }
        return max;
    }