数据结构——树（01二叉树的性质，代码练习）

二叉树的递归解法本质是 “分治思想”：将问题分解为左右子树的子问题，解决子问题后合并结果。因此方法1就是用递归。涉及到遍历整个树的可以使用广度优先遍历求解。

一、二叉树的性质

1.1二叉树的节点个数【2】

• 方法1（递归）：求出【左子树的节点个数】与【右子树的节点个数】+【root】即可。
• 方法2（广度优先遍历）：将访问result.push_back(p->val)换成sum++。即可。

int countNodes(TreeNode* root) {
        if(root==nullptr) return 0;
        else if(root->left==nullptr && root->right==nullptr) return 1;
        else if(root->left==nullptr) return countNodes(root->right)+1;
        else if(root->right==nullptr) return countNodes(root->left)+1;
        else return countNodes(root->left)+countNodes(root->right)+1;
    }

1.2计算二叉树的（最大深度&最小深度）【2&2】

二叉树的最大深度是指，从根节点root到最远的叶子节点的路径的节点数。（节点数=边数+1）

方法1（递归）：

• 空树：最大深度为 0（没有节点)
• 非空树：最大深度可以通过求【左子树和右子树的最大深度】得到解决，只需要在两个中找到最大值，再加上根节点的1即可。
• 例：要求root=3的这颗树的最大深度，可以转换为求root=9的最大深度（1）和root=20的最大深度（2）得出该树的最大深度为2+1=3。

方法2（广度优先遍历）：

• 树的最大深度即为树的层高。如本例中是层高为3的树，因此其最大深度为3.
• 用广度优先遍历按层遍历节点，每遍历完一层，深度就加 1。
• 难点：在遍历完一层后++，但是我怎么知道当前层有多少个节点呢？当前队列的大小即为当前层的节点数。

int maxDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        else return max(maxDepth(root->left),maxDepth(root->right)) +1;
    }

int maxDepth(TreeNode* root) {
        if(root==nullptr) return 0;

        //vector<int>result;
        queue<TreeNode*> Q;
        int level=0;//记录层数

        Q.push(root);
        while(!Q.empty()){
            int n=Q.size();//当前层的节点数
            for(int i=0;i<n;i++){
                TreeNode* p=Q.front();
                Q.pop();
                //result.push_back(p->val);
                if(p->left!=nullptr) Q.push(p->left);
                if(p->right!=nullptr) Q.push(p->right);
            }
            level++;//当前层遍历完后层数+1
        }
        return level;
    }

二叉树的最小深度是指从根节点到最近叶子节点的最短路径上的节点数量。

方法1（递归）：

• 空树：最小深度为0；
• 非空树：将问题转换为求【左子树的最小深度】与【右子树的最小深度】，只需要在两个中找到最小值，再加上根节点的1即可。
• 错误：没有考虑某一子树为空的特殊情况。当树的结构为 “左子树为空，右子树不为空” 时（或反之），会错误地将空的子树深度0参与最小值计算，导致结果为1。【最大深度无需考虑这个问题，因为总会选择较大的一方】
• 解决方法：当某一子树为空时，最小深度不能取空树的深度0，而应该取另一棵非空子树的深度。

方法2（广度优先遍历）：

• 找到距离根节点最近的叶子节点，该叶子节点所在的层数即为最小深度。
• 需要注意的是不能像寻找最大深度一样（遍历完该层后++），而是应该先++，然后遍历。当找到第一个叶子节点的时候就可以直接返回结果了。

int minDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        if(root->left==nullptr && root->right==nullptr) return 1;
        if(root->left==nullptr) return minDepth(root->right)+1;
        if(root->right==nullptr) return minDepth(root->left)+1;
        else  return min(minDepth(root->left), minDepth(root->right)) + 1;
    }

int minDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        
        queue<TreeNode*> Q;
        Q.push(root);
        int level=0;//最小深度
        
        while(!Q.empty()){
            int n=Q.size();//当前层的节点数
            level++;
            for(int i=0;i<n;i++){
                TreeNode* p=Q.front();
                Q.pop();
                //result.push_back(p=>val);
                if(p->left!=nullptr) Q.push(p->left);
                if(p->right!=nullptr) Q.push(p->right);
                //找到叶子节点，直接返回层数
                if(p->left==nullptr && p->right==nullptr) return level;
            }
            //level++;不能在当前层访问完再++，会中途退出，结果总是比真实结果+1。应该放在前面
        }
        return level;//理论上不会执行
    }

1.3判断二叉树（平衡&相等&对称）【1&1&1】

二叉树平衡：左右子树高度差不超过 1。

• 得到某节点的【左子树的最大深度】与【右子树的最大深度】，看【绝对值】是否差1。如果大于1则表示否。
• 递归检查其左子树和右子树是否也平衡，只有当所有节点都满足平衡条件时，整棵树才是平衡的。

int maxDepth(TreeNode* root){
    if(root==nullptr) return 0;
    return max(maxDepth(root->left),maxDepth(root->right)) +1;
}
bool isBalanced(TreeNode* root) {
    if(root==nullptr) return 1;
    //如果相差1则返回0
    if( abs(maxDepth(root->left)-maxDepth(root->right)) >1 ) return 0;
    //其他节点
    return isBalanced(root->left) && isBalanced(root->right);
}

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

• p为空，q为空——相等
• p不为空q为空，p为空q不为空——不相等
• p、q都为空——比较值（值不一样——不相等）
• 递归遍历左子树和右子树，只有当所有节点都满足条件时，才能判断相等。

bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==nullptr && q==nullptr) return 1;
        else if(p==nullptr || q==nullptr) return 0;
        else if(p->val!=q->val) return 0;
        else return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    }

对称的判断与相同的判断差不多，只是需要将最后递归判断修改一下即可。

bool isSame2(TreeNode* p,TreeNode* q){
   if(p==nullptr  && q==nullptr) return 1;
   else if(p==nullptr || q==nullptr) return 0;
   else if(p->val!=q->val) return 0;
   else return isSame2(p->left,q->right) && isSame2(p->right,q->left);
}
bool isSymmetric(TreeNode* root) {
    if (root==nullptr) return 1;
    else return isSame2(root->left,root->right);
}

1.4计算二叉树的（直径&坡度）【1&2】

二叉树的直径是指树中任意两个节点之间最长路径的长度。用节点之间的边数表示。
需要注意的是这条路径可能经过也可能不经过根节点 root 。

方法1（递归）：二叉树的直径是以下三种情况中的最大值：

• 情况 1：路径经过当前根节点，长度为【左子树最大深度 + 右子树最大深度】
• 情况 2：最长路径完全在左子树中，即左子树的直径。
• 情况 3：最长路径完全在右子树中，即右子树的直径。

方法2（递归）：上述方法每个节点的maxDepth会被重复计算。效率较低。可以在一次 DFS 遍历中，同时完成 “子树深度计算” 和 “直径更新”两个操作。
分步骤实现中，maxDepth会重复遍历子树（每个节点的深度计算都要重新遍历其下的所有节点）。
合并后，每个节点只被访问一次，深度计算和直径更新在同一次递归中完成。

//求二叉树的最大深度
int maxDepth(TreeNode* root){
    if(root==nullptr) return 0;
    else return max(maxDepth(root->left),maxDepth(root->right)) +1;
}
int diameterOfBinaryTree(TreeNode* root) {
    if(root==nullptr) return 0;
    return max({
        maxDepth(root->left) + maxDepth(root->right), //情况1：从左边最大深度，到根节点，到右边最大深度
        diameterOfBinaryTree(root->left), 
        diameterOfBinaryTree(root->right)
    });
}

• 节点4：l=0，r=0，depth=max(0,0)+1=1，M=0+0=0
• 节点5：l=0，r=0，depth=max(0,0)+1=1，M=0+0=0
• 节点2：l=1，r=1，depth=max(1,1)+1=2，M=1+1>0=2【4-2-5】
• 节点3：l=0，r=0，depth=max(0,0)+1=1，M=2
• 节点1：l=2，r=1，depth=max(1,2)+1=3，M=2+1>2=3【4-2-1-3 / 5-2-1-3】

int Max=0;//全局变量，直径
//dfs求深度
int dfs(TreeNode* root){
    if(root==nullptr) return 0;
    int leftdepth=dfs(root->left);
    int rightdepth=dfs(root->right);
    //同步更新直径：当前值or左深+右深
    Max=max(Max,leftdepth+rightdepth);
    //最大深度：
    return max(leftdepth,rightdepth)+1;
}
int diameterOfBinaryTree(TreeNode* root) {
    if(root==nullptr) return 0;
    Max=0;
    dfs(root);
    return Max;
}

一个树的节点的坡度定义为该节点【左子树的节点之和】和【右子树节点之和】的差的绝对值 。
没有左子树的，左子树的节点之和为 0 ；空结点的坡度是 0 。

方法1（递归）：分布计算得出结果
方法2（递归）：计算当前子树的和，同时累加当前节点的坡度。

//计算子树所有节点的和
int s(TreeNode* root){
    if(root==nullptr) return 0;
    else return s(root->left)+s(root->right)+root->val;
}
//单个节点的坡度值
int f(TreeNode* root){
    if(root==nullptr) return 0;
    else return abs(s(root->left)-s(root->right));
}
int findTilt(TreeNode* root) {
    if(root==nullptr) return 0;
    // 左子树的总坡度 + 右子树的总坡度+当前节点的坡度 
    else return findTilt(root->left)+findTilt(root->right)+f(root);
}

1.5计算二叉树的路径

返回所有从根节点到叶子节点的路径。

dfs在访问节点的过程中，完善字符串的格式（空时直接存当前节点值，非空时加"->"连接）。然后递归遍历左右子树，同时构建路径。

• 递归终止条件1：空节点直接返回
• 递归终止条件2：访问到叶节点，路径完整，加入结果集

vector<string> result;
void dfs(TreeNode* root,string path){
    if(root==nullptr) return ;

    //访问根节点
    if(path.empty()) path=path+to_string(root->val);
    else path=path+"->"+to_string(root->val);

    //访问到叶子节点结束
    if(root->left==nullptr && root->right==nullptr){
        result.push_back(path);
        return ;
    }
    //左右
    dfs(root->left,path);
    dfs(root->right,path);
}
vector<string> binaryTreePaths(TreeNode* root) {
    if(root==nullptr) return {};
    dfs(root,"");
    return result;
}