【LeetCode】104. Maximum Depth of Binary Tree 二叉树的深度 DFS BFS 递归方式迭代方式 JAVA

谁借莪１个温暖的怀抱￠ 2021-06-10 20:37 336阅读 0赞

## <table>   <tbody>    <tr>     <td><font>前言</font></td>    </tr>   </tbody>  </table> ##

这次的题目是二叉树的深度遍历，总体上来说吧，难度没有那么大，可是我就是再迭代的地方爬不出来了，有些题解也没有注释，讲解的也不是很清楚，所以就看起来有点麻烦

**题目传送门：** [点击此处][Link 1]

**题目截图：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>递归方式</font></td>    </tr>   </tbody>  </table> ##

public int maxDepth(TreeNode root) { 
        return root == null ? 0 : Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
    }

**PS：**  
虽然有人不是很理解代码为什么要写成一行，但是我觉得写成一行很得劲儿  
虽然会被嫌弃，但是我还是想这么干  
虽然我也嫌弃别人这么些，但是我也还是像这样写

## <table>   <tbody>    <tr>     <td><font>迭代方式</font></td>    </tr>   </tbody>  </table> ##

### DFS ###

不要吐槽我，注释稍后添加！！！！！！！！！！！！！！！！！！！！

public int maxDepth(TreeNode root) { 
        if(root == null) { 
            return 0;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> value = new Stack<>();
        stack.push(root);
        value.push(1);
        int max = 0;
        while(!stack.isEmpty()) { 
            TreeNode node = stack.pop();
            int temp = value.pop();
            max = Math.max(temp, max);
            if(node.left != null) { 
                stack.push(node.left);
                value.push(temp+1);
            }
            if(node.right != null) { 
                stack.push(node.right);
                value.push(temp+1);
            }
        }
        return max;
    }

### BFS ###

public int maxDepth(TreeNode root) { 
        if(root == null) { 
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int count = 0;
        while(!queue.isEmpty()) { 
            int size = queue.size();
            while(size > 0) { 
                TreeNode node = queue.poll();
                size--;
                if(node.left != null) { 
                    queue.offer(node.left);
                }
                if(node.right != null) { 
                    queue.offer(node.right);
                }
            }
            count++;
        }
        return count;
    }

[Link 1]: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/8fed052b84d846fe8bb3187f00468904.png