image

题目

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
题目地址

解题思路

迭代解法

我们先找子问题，一棵树的最大深度就是它左子树和右子树最大的深度的最大值。

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

那么怎么确认返回值呢，怎么返回左右子树的深度，我们可以想到每一层迭代都是向下的一层，我们只要每一次迭代都加1就可以了。得到了最终的代码。

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

迭代解法

关于迭代的解法，我们只要一层一层的遍历，遍历的过程中，记录层数即可。思路比较简单。代码如下

public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int preCount = 1;
        int pCount = 0;

        int level = 0;

        while (!q.isEmpty()) {
            TreeNode temp = q.poll();
            preCount--;

            if (temp.left != null) {
                q.offer(temp.left);
                pCount++;
            }
            if (temp.right != null) {
                q.offer(temp.right);
                pCount++;
            }

            if (preCount == 0) {
                preCount = pCount;
                pCount = 0;
                // System.out.println();
                level++;
            }
        }
        return level;
    }