首页 > 编程语言(其他) > 【LeetCode】111. Minimum Depth of Binary Tree

【LeetCode】111. 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. 递归遍历,求每棵子树的最小路径
  2. 宽度优先搜索,或者说层次遍历,遍历树的每一层,找到了一个叶子节点就直接返回层数

代码

解法1 直接递归:

int minDepth(TreeNode* root) {
        if(root==0) return 0;
        if(root->left==0&&root->right==0) return 1;
        int l = minDepth(root->left);
        int r = minDepth(root->right);
        if(l==0) return r+1;
        if(r==0) return l+1;
        return l<r?l+1:r+1;
    }

解法2 宽度优先:

class Solution {
public:

    int minDepth(TreeNode* root) {
        if(root==0) return 0;
        queue<pair<TreeNode*,int> > q;
        q.push(make_pair(root,1));
        while(!q.empty()) {
            pair<TreeNode*,int> elem = q.front();
            TreeNode* p = elem.first;
            int level = elem.second;
            q.pop();
            if(p->left==0&&p->right==0) return level;
            if(p->left!=0) q.push(make_pair(p->left, level+1));
            if(p->right!=0) q.push(make_pair(p->right, level+1));
        }
        return 0;
    }
}
作者:zgljl2012 发表于2017/1/9 10:13:54 原文链接
阅读:131 评论:0 查看评论
分类: 编程语言(其他) 标签: