[每日一道小算法（三十八）][树] 二叉树的深度（剑指offer）

Myth丶恋晨 2023-07-06 06:19 28阅读 0赞

前言：  
这几天一直在做树类型的题，所以这几天都是关于树的，希望做完这些题能有所收获吧。

### 题目描述 ###

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。‘

### 题目解析 ###

刚看这道题我就想到了我以前做过的从上到下打印二叉树，这两道题很相似。这道题就是在从上到下打印二叉树的基础上统计层数的个数呗，那么解决就很简单了。用一个变量来计数就可以了。  
上面这是一道解题算法，但是需要辅助空间，所以我们还有一种使用递归的方法来实现。我们分别做左右子树进行遍历，计算左右子树的最大深度，最后在针对左右子树来做一个最大值对比就可以解决问题了。  
下面贴出两种方法，仅供参考：

### 代码样例 ###

#### 方法一（非递归解法） ####

package com.asong.leetcode.TreeDepth;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    /** * 二叉树的深度 */
    public class Solution { 
        public int TreeDepth(TreeNode root) { 
            if(root == null)
            { 
                return 0;
            }
            int row = 0;
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            while(!queue.isEmpty())
            { 
                int size = queue.size();
                for (int i = 0; i < size; i++) { 
                    TreeNode node = queue.poll();
                    if(node.left!=null)
                    { 
                        queue.offer(node.left);
                    }
                    if(node.right!=null)
                    { 
                        queue.offer(node.right);
                    }
                }
                row++;
            }
            return row;
        }
    }

#### 方法二（递归解法） ####

/** * 二叉树的深度（递归解法） */
    public class Solution1 { 
        public int TreeDepth(TreeNode root) { 
            if(root == null)
            { 
                return 0;
            }
            int left = TreeDepth(root.left);
            int right = TreeDepth(root.right);
            //最后需要+1操作，因为不包含根节点，所以需要加上
            return Math.max(left,right)+1;
        }
    }