题解 | #二叉树的深度#

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
示例1
输入：{1,2,3,4,5,#,6,#,#,7}
返回值：4

题目分析

要想获得树的最长路径，需要遍历树的所有路径，在一条路径中，每经过一个结点，深度加1，选出其中最长的，如图示例1，一共有三条路径，里面最长的路径为1-2-5-7，深度为4.

遍历树的方法有递归和非递归两种。

解题思路

方法1：递归
在递归遍历的过程中，需要在左右子树之间进行选择，当前结点不为空时，深度需要加一，因为要深度最大的路径，所以选取左右子树中最大的那个，递归的终止条件为当前结点为空。

方法2：非递归
树的非递归方法中，有使用stack进行深度遍历，也有使用queue进行层次遍历，因为涉及到树的最大深度，所以选择层次遍历方法，记录遍历的层数，直到最后一层。

代码实现

方法1：递归

    public int TreeDepth(TreeNode root) {
        if(root == null) return 0;
        // 获取左子树高度（包括当前结点）
        int left = TreeDepth(root.left)+1;
        // 获取右子树高度
        int right = TreeDepth(root.right)+1;
        // 返回更高的子树作为深度
        return Math.max(left, right);
    }

时间复杂度：O(n)，需要遍历整个树的结点；
空间复杂度：O(n)，在方法中使用的常数的变量，选择递归的深度作为空间复杂度，最差情况下，树退化成链表，递归的深度为n；

方法2：非递归

    public int TreeDepth(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(root);
        // 记录最大的深度
        int depth = 0;
        // 计算当前层的结点数
        int count = 0;
        // 每一层的结点数
        int size = queue.size();
        while(!queue.isEmpty()) {
              // 使用队列来存储结点，弹出某一层结点
              TreeNode t = queue.poll();
              count++;
              // 将此结点的左右子节点放入队列中，作为下一层遍历
              if(t.left!=null)  queue.add(t.left);
              if(t.right!=null) queue.add(t.right);
              // 当已经遍历完一层结点，更新相应值
              if(count == size) {
                   depth++;
                   count = 0;
                   size = queue.size();
              }
        }
        return depth;
    }

时间复杂度：O(n)，需要遍历完树的所有结点；
空间复杂度：O(n)，队列中存储的结点有出有入，当前一个结点出队列时，会加入它的左右子节点，队列中存储的最多的结点数是二叉树中一层最多的结点，而一层结点最多占树的总结点的1/2（满二叉树），即n/2。