《剑指offer》 第55-1题 二叉树深度

思路1：递归
写法构思：传入某节点，调用该方法，返回的应该是以传入节点为根节点的树的深度，而树的深度，肯定和左右子树深度有关，所以进入这个方法后，就包含了左右子树的深度（而要得到左右子树的深度，肯定又是以左右子节点为根节点，再次调用该方法深度获取的，因此此时进行递归），并且还有由一个左右深度比较的过程，然后取较大值，这个较大值就是该节点左右子树深度较深的值，以该值+1作为返回值，就是该节点的深度。

因此，方法名TreeDepth，在方法中，申明两个变量分别记录得到的左右子树深度。

int left = node.TreeDpth(Root.left);// 显然需要把当前节点的左节点传入，进行递归调用
int right = node.TreeDpth(Root.right);

然后进行比较,较大值+1作为返回值。

 return left > right ? left + 1 : right + 1;

再考虑递归结束条件，当传入节点的左右子节点，有为空的时候，应该返回0；这样就表示，传入的节点，左右子树为空时，左右子树的深度为0。显然这部分代码应该在调用递归之前执行，到了空直接return，不满足空就说明还有子树，继续递归

 if(Root == null){
            return 0;
        }

因此将代码组合起来，就是答案

import java.util.Queue;
import java.util.LinkedList;
public class Solution {
   public int TreeDepth(TreeNode Root)
    {
        if(Root == null){
            return 0;
        }
        int left = TreeDepth(Root.left);
        int right = TreeDepth(Root.right);
        return left > right ? left + 1 : right + 1;
    }
}

2.非递归写法
写法构思：利用的队列，首先给入的是根节点，使其入队，遍历某个节点时，将该节点出队，并将该节点的所有子节点入队，当同一深度的节点都遍历完的时候，深度++，所以设depth是深度。count是已经当前层（同一深度层）出队列的节点数（已遍历），nextcount是当前层的节点总数。所以当count等于nextcount就意味着当前层已遍历完，需要将当前节点数count置为0，在再弹出节点时。进行深度++操作。并重新更新nextcount的值
因此需要不断的从队列中取、放节点。通过while进行循环，而队列为空时，说明所有节点都遍历了，返回最终的depth。而只要队列不为空，就需要进行遍历和后续的操作。

因此，首先创建队列，将根节点入队

queue.add(root);

判断队列是否为空（此时进入while循环过程），将根（当前节点）节点出队，count++；

TreeNode top = queue.poll();
 count++;

然后将根节点（当前节点）的子节点入队

 if(top.left != null){
       queue.add(top.left);
            }
if(top.right != null){
       queue.add(top.right);
            }

判断count和nextcount大小，不相等说明同一深度层没有遍历完，继续while过程，进行出队，count++，直到count递增到和nextcount相同时，说明同一深度层遍历完，此时深度depth++，并且需要将count重新置为0

 if(count == nextCount){
                nextCount = queue.size();
                count = 0;
                depth++;
            }

注意此时的队列中，由于同一深度层A全部遍历完并且出队，而且在A层遍历的时候，已经将A层子节点全部入队了，此时队列中存放的是深度为A+1层的所有节点，所以此时应给nextcount赋值为队列的size，更新的nextcount就是深度A+1层的所有节点数，而下次从队列中取节点时，也是A+1层的节点了（完成了一个深度为A的遍历）.nextcount的初始值应该为1（就根节点一个），第一次是根节点入队出队，队列长度为1.

//因此赋初始值时  这是在while过程外赋值
 int depth = 0, count = 0, nextCount = 1;

因此，考虑根节点为空的情况，再将思路各个部分组合起来就是答案

import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    public int TreeDepth(TreeNode root) {
         if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int depth = 0, count = 0, nextCount = 1;
        while(queue.size()!=0){
            TreeNode top = queue.poll();
            count++;
            if(top.left != null){
                queue.add(top.left);
            }
            if(top.right != null){
                queue.add(top.right);
            }
            if(count == nextCount){
                nextCount = queue.size();
                count = 0;
                depth++;
            }
        }
        return depth;
    }
}
//这里其实还可以写成，每添加一个，就让深度++，最后深度的变量赋值给nextcount

5.20更新

对于非递归层次遍历写法，可以有如下写法。

public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //BFS的层次遍历思想，记录二叉树的层数，
        //遍历完，层数即为最大深度
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int maxDepth = 0;
        while (!queue.isEmpty()) {
            maxDepth++;
            int size = queue.size();//先获取本层的节点数，然后遍历，之前的是边遍历，边判断
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return maxDepth;
    }

  使用栈也是可以解题。只不过入栈时还要带上该节点的深度的信息。也就是说，入栈的不是节点，而是一个包含节点和该节点深度的一个对象。所以要建一个类。
力扣题解

    /**
     * DFS迭代实现二叉树最大深度
     * 时间复杂度O(n)
     * 空间复杂度:线性表最差O(n)、二叉树完全平衡最好O(logn)
     *
     * @param root 根节点
     * @return 最大深度
     */
    private static int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<Pair<TreeNode, Integer>> stack = new LinkedList<>();
        stack.push(new Pair<>(root, 1));
        int maxDepth = 0;
        //DFS实现前序遍历，每个节点记录其所在深度
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> pair = stack.pop();
            TreeNode node = pair.first;
            //DFS过程不断比较更新最大深度
            maxDepth = Math.max(maxDepth, pair.second);
            //记录当前节点所在深度
            int curDepth = pair.second;
            //当前节点的子节点入栈，同时深度+1
            if (node.right != null) {
                stack.push(new Pair<>(node.right, curDepth + 1));
            }
            if (node.left != null) {
                stack.push(new Pair<>(node.left, curDepth + 1));
            }
        }
        return maxDepth;
    }