二叉樹的最小深度

題目

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版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。