跳到主要内容

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.

分析

递归版

// Minimum Depth of Binary Tree
// 递归版,时间复杂度O(n),空间复杂度O(logn)
public class Solution {
public int minDepth(TreeNode root) {
return minDepth(root, false);
}
private static int minDepth(TreeNode root, boolean hasbrother) {
if (root == null) return hasbrother ? Integer.MAX_VALUE : 0;

return 1 + Math.min(minDepth(root.left, root.right != null),
minDepth(root.right, root.left != null));
}
}

迭代版

// Minimum Depth of Binary Tree
// 迭代版,时间复杂度O(n),空间复杂度O(logn)
public class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;

int result = Integer.MAX_VALUE;
Stack<Pair> s = new Stack<>();
s.push(new Pair(root, 1));

while (!s.empty()) {
final Pair p = s.pop();
TreeNode node = p.node;
int depth = p.depth;

if (node.left == null && node.right == null)
result = Math.min(result, depth);

if (node.left != null && result > depth) // 深度控制,剪枝
s.push(new Pair(node.left, depth + 1));

if (node.right != null && result > depth) // 深度控制,剪枝
s.push(new Pair(node.right, depth + 1));
}

return result;
}

static class Pair {
TreeNode node;
int depth;
public Pair(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
}

相关题目