本文共 1255 字,大约阅读时间需要 4 分钟。
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
返回它的最小深度 2.
求最小深度,分三种情况。如果左右子树都不为空,则递归求他们两者的最小值,若左(右)子树不为空,则递归下去。
Java:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public int minDepth(TreeNode root) { if(root==null) return 0; if(root.left!=null&&root.right!=null) return Math.min(minDepth(root.left)+1,minDepth(root.right)+1); else if(root.right!=null) return minDepth(root.right)+1; else return minDepth(root.left)+1; }}
C++:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: int minDepth(TreeNode* root) { if(root==NULL) return 0; if(root->left&&root->right) return min(minDepth(root->left),minDepth(root->right))+1; else if(root->right) return minDepth(root->right)+1; else return minDepth(root->left)+1; }};
转载地址:http://pvaen.baihongyu.com/