admin 管理员组

文章数量: 887021

二叉树

文章目录

  • 问题：二叉树的最大深度
    • 解题思路
    • C++代码
  • 问题：二叉树的最小深度
    • 解题思路
    • C++代码

问题：二叉树的最大深度

问题链接

解题思路

采用递归的思路，如果root为NULL，返回0，否则返回1+max{左子树深度，右子树深度}

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 maxDepth(TreeNode* root) {//如果root为NULL，返回0，否则返回1+max{左子树深度，右子树深度}return root ? 1+max(maxDepth(root->left), maxDepth(root->right)) : 0;}
};

问题：二叉树的最小深度

问题链接

解题思路

采用递归的思想，注意单分支的处理

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) return 0;//空树情况int d1 = minDepth(root->left);int d2 = minDepth(root->right);if(root->left && root->right) //左右孩子都在return 1 + min(d1, d2);else if(!root->left && !root->right)//root是叶节点return 1;else//只有一个分支，d1 = 0 或者 d2 = 0return 1 + d1 + d2;}
};

本文标签： 二叉树

版权声明：本文标题：二叉树 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1686575455h12312.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。