二叉树的最小深度

题目

https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

二叉树定义如下：

// Definition for a binary tree node. class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;} }

普通版题解

• 时间复杂度O(n)，需要遍历所有的节点。
• 空间复杂度为O(h)。其中，h 表示二叉树的高度，也就是递归使用的系统调用栈的高度。

class Solution {public int minDepth(TreeNode root) {if (root != null) {if (root.left == null || root.right == null) {// 根部只有一个孩子或没有孩子return Math.max(minDepth(root.left), minDepth(root.right)) + 1;} else { // 根部有两个孩子return Math.min(minDepth(root.left), minDepth(root.right)) + 1;}} else return 0;} }

进阶版：根据 Morris 遍历改写

• 时间复杂度O(n)，需要遍历所有的节点。
• 空间复杂度为O(1)。
  
  

代码（含测试用例）

package chapter_3_binarytreeproblem;public class Problem_02_MinDepth {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static int minDepth1(Node head) {if (head == null) {return 0;}return process(head, 1);}public static int process(Node cur, int level) {if (cur.left == null && cur.right == null) {return level;}if (cur.left != null && cur.right == null) {return process(cur.left, level + 1);}if (cur.left == null && cur.right != null) {return process(cur.right, level + 1);}return Math.min(process(cur.left, level + 1), process(cur.right, level + 1));}// 根据 morris 遍历改写public static int minDepth2(Node head) {if (head == null) {return 0;}Node cur = head;Node mostRight = null;int curLevel = 0;int minHeight = Integer.MAX_VALUE;while (cur != null) {mostRight = cur.left;if (mostRight != null) { // 当前cur有左子树，能到达两次// cur左子树上，右边界的节点个数int leftTreeRightSize = 1;// 找到cur左子树上最右的节点while (mostRight.right != null && mostRight.right != cur) {leftTreeRightSize++;mostRight = mostRight.right;}if (mostRight.right == null) {// 第一次到达cur，那么下一个节点的level必然+1curLevel++;mostRight.right = cur;cur = cur.left;continue;} else {// 第二次到达cur，那么下一个节点的level=curLevel-leftTreeRightSize，此时检查mostRight是不是叶节点。记录答案if (mostRight.left == null) {minHeight = Math.min(minHeight, curLevel);}curLevel -= leftTreeRightSize;mostRight.right = null;}} else {// 当前xue没有欧左子树，只能到达一次，那么下一个节点的level必然+1curLevel++;}cur = cur.right;}int finalRight = 1;cur = head;while (cur.right != null) {finalRight++;cur = cur.right;}// 最后不要忘了单独看看整棵树的最右节点是不是叶节点if (cur.left == null && cur.right == null) {minHeight = Math.min(minHeight, finalRight);}return minHeight;}public static void main(String[] args) {Node node1 = new Node(1);Node node2 = new Node(2);node1.right = node2;Node node3 = new Node(3);node2.left = node3;Node node4 = new Node(4);Node node5 = new Node(5);node3.left = node4;node3.right = node5;System.out.println(minDepth2(node1));}}

---

二叉树的最大深度

剑指 Offer 55 - I. 二叉树的深度

题解

一行代码解决！

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

总结

以上是生活随笔为你收集整理的左神算法：二叉树的最大 / 最小深度（普通+Morris遍历进阶）（Java版）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。