LeetCode 104 二叉树的最大深度及N叉树的最大深度 及扩展(平衡二叉树)

二叉树的最大深度分两种方法：递归和迭代

递归版本如下：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) {return 0;}
        int left_height = maxDepth(root->left);
        int right_height = maxDepth(root->right);

        int height = 1 + max(left_height, right_height);
        
        return height;
    }
};

递归简化版本如下：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) {return 0;}
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

迭代版本如下(层序遍历)：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) {return 0;}

        int depth = 0;
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()) {
            int size = q.size();
            ++depth;

            while(size--) {
                TreeNode *tmp_node = q.front();
                q.pop();
                if(tmp_node->left) {q.push(tmp_node->left);}
                if(tmp_node->right) {q.push(tmp_node->right);}
            }
        }
        return depth;
    }
};

N叉树的最大深度同二叉树非常相似，就是判断左右孩子条件从两个if(遍历左右孩子)变成了遍历所有孩子

递归

class Solution {
public:
    int maxDepth(Node* root) {
        if(!root) {return 0;}

        int max_depth = 0;
        for(int i = 0; i < root->children.size(); ++i) {
            max_depth = max(max_depth, maxDepth(root->children[i]));
        }

        return max_depth + 1;
    }
};

迭代

class Solution {
public:
    int maxDepth(Node* root) {
        if(!root) {return 0;}

        int depth = 0;
        queue<Node*> q;
        q.push(root);

        while(!q.empty()) {
            int size = q.size();
            ++depth;
            while(size--) {
                Node *tmp = q.front();
                q.pop();
                for(int i = 0; i < tmp->children.size(); ++i) {
                    if(tmp->children[i]) {
                        q.push(tmp->children[i]);
                    }
                }
            }
        }
        return depth;
    }
};

平衡二叉树

会了上面的，其实做法很简单，递归的去计算各节点左右子树的高度差即可

递归做法

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root) {return true;}
        return abs(getHeight(root->left) - getHeight(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }

    int getHeight(TreeNode* root) {
        if(!root) {return 0;}
        return 1 + max(getHeight(root->left), getHeight(root->right));
    }
};

迭代做法

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root) {return true;}
        return abs(getHeight(root->left) - getHeight(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }

    int getHeight(TreeNode* root) {
        if(!root) {return 0;}
        queue<TreeNode*> q;
        int depth = 0;
        q.push(root);

        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                TreeNode* tmp_node = q.front();
                q.pop();
                if(tmp_node->left) {q.push(tmp_node->left);}
                if(tmp_node->right) {q.push(tmp_node->right);}
            }
            ++depth;
        }
        return depth;
    }
};