剑指OfferJZ38：二叉树的深度-java版

矫情吗；* 2023-01-21 05:23 117阅读 0赞

### 剑指OfferJZ38：二叉树的深度-java版 ###

*   *  JZ38：输入一棵二叉树，求该树的深度。

## JZ38：输入一棵二叉树，求该树的深度。 ##

从根节点开始统计，先递归到左孩子，再递归右孩子，此后每个节点都是同样的规律  
**对于每一个节点，先遍历当前节点的左孩子（直到叶子节点），再遍历当前节点的右孩子（直到叶子结点）**  
实际在写代码时也**让叶子结点遍历它的左节点（null）和右节点（null）**，其实都是空，返回0；这样做是为了标记递归的终止条件，不影响结果  
然后返回到上一层，直到到达根节点，每返回一层，返回结果+1  
（如图：从根节点1先递归到左孩子2，2已经是叶子结点了，此时再让叶子结点2遍历它的左孩子和右孩子，都是null，返回0；节点2返回到上一层节点1（根节点），只返回了一层，返回结果为1）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]

（从根节点1再递归到右孩子3；从节点3先递归到3的左孩子4（叶子结点），再让叶子结点4遍历它的左孩子和右孩子，都是null，返回0；节点4返回到上一层节点3，返回了一层，返回结果为1；然后递归到3的右孩子，为null，返回0；3节点这里两个返回结果取最大的那个结果1；节点3继续返回到上一层节点1（根节点），返回结果再+1，结果为2；1节点（根节点）这里两个返回结果同样的取最大的那个结果2（代表3节点和4节点）；最终结果要加上根节点，因此二叉树的深度为2+1=3）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]

public class Solution { 
        public int TreeDepth(TreeNode root) { 
            //TreeNode表示树（Tree）中的一个节点
            if(root==null){ //如果当前节点为空
                return 0;
            }
            //treeDepth　求解树的深度,这里的深度(depth)指的是根节点到最深叶子点的距离
            //递归求出左子树的深度TreeDepth(root.left)
            //递归求出右子树的深度TreeDepth(root.right)
            return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
            
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 2]

再试一个：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][20210526112621930.gif_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]: /images/20221020/a591ef3caf44429e92560b19e2fd75b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]: /images/20221020/5fffeb9f581f4bf187baa40952f9ef67.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 2]: /images/20221020/0c51d1f972e44bc0a71f9716778b08ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 3]: /images/20221020/c849e1c95c18462aa93e5cee852ffe56.png
[20210526112621930.gif_pic_center]: /images/20221020/9d6a32c0e7d34e94a80a711d12746b93.png