lc104 二叉树的最大深度

首先需要知道深度与高度的区别，对于一个二叉树中的节点

• 深度： 根节点到该节点的距离
• 高度： 该节点到最底层叶节点的距离
  而求最大深度无异于求根节点的高度，二者是相等的

之前使用层序遍历的迭代法做过这道题：[[day14#lc104 二叉树的最大深度]]
本次使用递归的方式来解决

后序

递归中稍微简单一些的方式是求根节点的最大高度，使用后序遍历（从下到上不断累加）

class Solution {
public:
    int maxDepth(TreeNode* root) {      //在使用递归时，这里叫root并不合适，叫node好一些
        if(root==NULL) 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 result;
    void getdepth(treenode* node, int depth) {
        result = depth > result ? depth : result; // 中

        if (node->left == NULL && node->right == NULL) return ;

        if (node->left) { // 左
            depth++;    // 深度+1
            getdepth(node->left, depth);
            depth--;    // 回溯，深度-1
        }
        if (node->right) { // 右
            depth++;    // 深度+1
            getdepth(node->right, depth);
            depth--;    // 回溯，深度-1
        }
        return ;
    }
    int maxdepth(treenode* root) {
        result = 0;
        if (root == NULL) return result;
        getdepth(root, 1);
        return result;
    }
};

相似题目 lc559 n叉树的最大深度

递归法

class Solution {
public:
    int maxDepth(Node* root) {
        if(root == NULL) return 0;
        int max_height = 0;
        for(int i=0;i<root->children.size();i++){
            max_height = max(max_height,maxDepth(root->children[i]));
        }
        int height = 1 + max_height;
        return height;
    }
};

迭代法

class Solution {
public:
    int maxDepth(Node* root) {
        queue<Node*> que;
        int depth = 0;
        if(root != NULL) que.push(root);
        while(!que.empty()){
            int size = que.size();
            depth++;
            while(size--){
                Node* node = que.front();
                que.pop();
                for(int i=0;i<node->children.size();i++){
                    if(node->children[i]) que.push(node->children[i]);
                }
            }
        }
        return depth;
    }
};

lc111 二叉树的最小深度

之前做过这道题目的迭代法解法：[[day14#lc111 二叉树的最小深度]]，这次主要看一下递归法
注意只有当节点没有任何子节点时才会被视作叶子节点

class Solution {
public:
    int minDepth(TreeNode* root) {  //此处叫root并不合适，最好叫node
        if(root == NULL) return 0;
        int minLeft = minDepth(root->left);
        int minRight = minDepth(root->right);
        if(root->left == NULL && root->right != NULL){
            return 1 + minRight;
        }
        if(root->left != NULL && root->right == NULL){
            return 1 + minLeft;
        }
        return 1 + min(minLeft,minRight);
    }
};

lc222 完全二叉树的节点个数

对于普通二叉树，我们获取节点个数需要O(n)的时间，但是对于完全二叉树，可以利用其特性寻找其子满二叉树。然后利用公式直接计算节点个数

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==NULL) return 0;
        int leftDepth = 0;
        int rightDepth = 0;
        TreeNode* cur_left = root->left;
        TreeNode* cur_right = root->right;
        while(cur_left){
            leftDepth++;
            cur_left = cur_left->left;
        }
        while(cur_right){
            rightDepth++;
            cur_right = cur_right->right;
        }
        //完全二叉树可以直接使用2^h-1计算
        if(leftDepth==rightDepth){
            return (2 << leftDepth) - 1; //The same as 2^(leftDepth + 1) - 1, 
                                            //remeber we start at leftDepth=0
        }
        int leftCount = countNodes(root->left); //左
        int rightCont = countNodes(root->right); //右
        return 1 + leftCount + rightCont;       //中
    }
};

其时间复杂度为\(O(logn * logn)\)。