## day16 - 二叉树part03

day16 - 二叉树part03

力扣104. 二叉树的最大深度

思路：最大深度，即为顶点高度。

如果想求高度，人类思维的角度，就是从底层开始算，往上一层+1，加到顶点就是高度，也就是最大深度。

因此要用后序遍历，这样可以左右根的顺序进行遍历，从而一层一层向上返回结果，返回到根节点的时候就计算出来了最大深度

代码

class Solution {
public:

    int getHeight(TreeNode* node)
    {
        //如果节点是空，那么高度的0
        if (node == nullptr)
        {
            return 0;
        }
        //计算左孩子的高度
        int lh = getHeight(node->left);
        //计算右孩子的高度
        int rh = getHeight(node->right);
        //当前节点的高度，等于1+左右孩子最大的高度
        int height = 1 + max(lh, rh);
        return height;
    }


    int maxDepth(TreeNode* root) {
        return getHeight(root);
    }
};

力扣559. N叉树的最大深度

思路：就是把之前只有两个孩子的情况，换成for循环。遍历出最大值。

class Solution {
public:

    int getHeight(Node* node)
    {
        if (node == nullptr)
        {
            return 0;
        }
        int maxHeight = 0;
        for (int i = 0; i < node->children.size(); i++)
        {
            maxHeight = max(maxHeight, getHeight(node->children[i]));
        }
        return 1 + maxHeight;
    }


    int maxDepth(Node* root) {
        
        return getHeight(root);
    }
};

力扣222. 完全二叉树的节点个数

思路：判断二叉树是否是满二叉树，如果是，则直接使用公式2的n次方减1返回节点数量，使用位运算。

如果不是，则继续判断左右子树是否是满二叉树，直到是为止，因为叶子节点必定是慢二叉树。

代码

class Solution {
public:

    int getNum(TreeNode* node)
    {
        if (node == nullptr)
        {
            return 0;
        }
        TreeNode* left = node->left;
        TreeNode* right = node->right;
        int leftdepth = 0;
        int rightdepth = 0;
        while (left)
        {
            left = left->left;
            leftdepth++;
        }
        while(right)
        {
            right = right->right;
            rightdepth++;
        }
        if (leftdepth == rightdepth)
        {
            return (2<<leftdepth) - 1;
        }
        else
        {
            return getNum(node->left) + getNum(node->right) +1;
        }
    }

    int countNodes(TreeNode* root) {
        return getNum(root);
    }
};