欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的最小、最大深度以及平衡二叉树

程序员文章站 2022-07-14 18:07:57
...

**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.
代码如下:

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==NULL)
            return 0;
        int left = minDepth(root->left);
        int right = minDepth(root->right);
        if(root->left==NULL&&root->right==NULL)
            return 1;
        if(root->left==NULL)
            left = INT_MAX;
        if(root->right==NULL)
            right = INT_MAX;
        return left<right ? left + 1 : right + 1;
    }
};

**104. Maximum Depth of Binary Tree **
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)
          return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return left>right ? left+1:right+1;
    }
};

**110. Balanced Binary Tree **
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
代码如下:

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root==NULL)
          return true;
        int mLeft = maxDepth(root->left);
        int mRight = maxDepth(root->right);
        
        if(abs(mLeft-mRight)>1)
          return false;
        else
          return isBalanced(root->left)&&isBalanced(root->right);
    }
    int maxDepth(TreeNode* node)
    {
        if(node==NULL)
          return 0;
        int left = maxDepth(node->left);
        int right = maxDepth(node->right);
        return left>right? left+1:right+1;
    }
};