代码随想录|二叉树part 03

求普通二叉树的节点数量
要点：将子节点的个数记录到父节点，使用后序遍历
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)return 0;
        int left1=maxDepth(root->left);
        int right1=maxDepth(root->right);
        int num=1+left1+right1;
        return num;
    }
};


完全二叉树思路：

完全二叉树：除最后一层外，其他层都是满的，最后一层从左到右都是满的

先判断左右子树是否为满二叉树，通过求得满二叉树的深度，利用公式计算节点数，将节点数记录在父节点，若不是满二叉树，则继续遍历
此时父节点记录的为整个子树的节点个数
判断满二叉树：向左递归的深度与向右递归深度相等
，递归时仅左子树的左节点和右子树的右节点
递归终止条件：1、节点为空	2、遇见满二叉树，返回节点个数给父节点

2<<n :意味着当n=0时，2<<n=1，当n=1时，2<<n=2


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==NULL)return 0;
        TreeNode *leftkey=root->left;
        TreeNode *rightkey=root->right;
        int leftnum=0,rightnum=0;
        while(leftkey)
        {
            leftkey=leftkey->left;
            leftnum++;
        }
        while(rightkey)
        {
            rightkey=rightkey->right;
            rightnum++;
        }
        if(leftnum==rightnum)//判断是否为满二叉树，递归返回条件之一
        {
            return (2<<rightnum)-1;
        }
        int left1=countNodes(root->left);
        int right1=countNodes(root->right);
        int num=left1+right1+1;//父节点记录该子树的全部节点数
        return num;
    }
};

平衡二叉搜索树（map\set\multiset\multimap)
任意节点左子树与右子树的高度差小于等于1

要点：
对左右子树分别统计其高度，计算高度差，判断是否符合平衡二叉树，符合返回最大高度，不符合返回-1

class Solution {
public:
    int getheight(TreeNode *root)
    {
        if(root==NULL)return 0;//结束条件
        int leftheight=getheight(root->left);//统计左方向子树高度，若符合平衡二叉返回最大高度，不符合，返回-1
        if(leftheight==-1)return -1;
        int rightheight=getheight(root->right);
        if(rightheight==-1)return -1;
        int height;
        if(abs(leftheight-rightheight)>1)height=-1;
        else{
            height=1+max(leftheight,rightheight);
        }
        return height;
    }
    bool isBalanced(TreeNode* root) {
        int height=getheight(root);
        if(height==-1)
        return false;
        else
        return true;
    }
};

要点：
利用前序遍历，用int数组记录单条路径
递归返回条件：遇到了叶子节点，将该路径记录，并返回
单层递归逻辑：1、将该节点的数值加入int数组
2、若左节点不为空，进入递归，递归结束后，弹出int数组的最后一个节点，即回溯到上一个节点，转为右节点进行递归
将int数组转为string：to_string(vector<int>)，再将string加入数组

class Solution {
public:
    void getpath(TreeNode *root,vector<int>&path,vector<string>&res)
    {
        path.push_back(root->val);//中
        if(root->left==NULL&&root->right==NULL)
        {
            string s;
            for(int i=0;i<path.size()-1;i++)
            {
                s+=to_string(path[i]);
                s+="->";
            }
            s+=to_string(path[path.size()-1]);
            res.push_back(s);
            return;
        }
        if(root->left)
        {
            getpath(root->left,path,res);
            path.pop_back();//回溯，将该叶子节点弹出，回到父节点
        }
        if(root->right)
        {
            getpath(root->right,path,res);
            path.pop_back();
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<int>path;
        vector<string>res;
        getpath(root,path,res);
        return res;
    }
};

所有父节点的左叶子之和
要点：
当此节点为叶子节点时，返回的值为0
此节点为父节点时，若他的左节点不为空且左节点的左右节点均为空，说明遇到了左叶子节点，记录下来

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root==NULL)return 0;
        if(root->left==NULL&&root->right==NULL)return 0;//叶子节点
        int leftsum=sumOfLeftLeaves(root->left);
        if(root->left!=NULL&&root->left->left==NULL&&root->left->right==NULL)//左叶子节点
        leftsum=root->left->val;
        int rightsum=sumOfLeftLeaves(root->right);
        return leftsum+rightsum;
    }
};