Minimum Depth of Binary Tree

描述

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

分析

无

递归版

  1. // Minimum Depth of Binary Tree
  2. // 递归版，时间复杂度O(n)，空间复杂度O(logn)
  3. public class Solution {
  4.     public int minDepth(TreeNode root) {
  5.         return minDepth(root, false);
  6.     }
  7.     private static int minDepth(TreeNode root, boolean hasbrother) {
  8.         if (root == null) return hasbrother ? Integer.MAX_VALUE : 0;
  10.         return 1 + Math.min(minDepth(root.left, root.right != null),
  11.                 minDepth(root.right, root.left != null));
  12.     }
  13. }

迭代版

  1. // Minimum Depth of Binary Tree
  2. // 迭代版，时间复杂度O(n)，空间复杂度O(logn)
  3. public class Solution {
  4.     public int minDepth(TreeNode root) {
  5.         if (root == null) return 0;
  7.         int result = Integer.MAX_VALUE;
  8.         Stack<Pair> s = new Stack<>();
  9.         s.push(new Pair(root, 1));
  11.         while (!s.empty()) {
  12.             final Pair p = s.pop();
  13.             TreeNode node = p.node;
  14.             int depth = p.depth;
  16.             if (node.left == null && node.right == null)
  17.                 result = Math.min(result, depth);
  19.             if (node.left != null && result > depth) // 深度控制，剪枝
  20.                 s.push(new Pair(node.left, depth + 1));
  22.             if (node.right != null && result > depth) // 深度控制，剪枝
  23.                 s.push(new Pair(node.right, depth + 1));
  24.         }
  26.         return result;
  27.     }
  29.     static class Pair {
  30.         TreeNode node;
  31.         int depth;
  32.         public Pair(TreeNode node, int depth) {
  33.             this.node = node;
  34.             this.depth = depth;
  35.         }
  36.     }
  37. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/binary-tree/recursion/minimum-depth-of-binary-tree.html