最长连续序列路径

给你一棵指定的二叉树的根节点 root ，请你计算其中 最长连续序列路径 的长度。
最长连续序列路径 是依次递增 1 的路径。该路径，可以是从某个初始节点到树中任意节点，通过「父 - 子」关系连接而产生的任意路径。且必须从父节点到子节点，反过来是不可以的。

class Solution {
public: 
    int sum=1;
    void dfs(TreeNode*root,TreeNode*p,int cnt){
        if(!root)return;
        if(p){
            if(p->val+1==root->val) cnt++;
            else cnt=1;
            if(cnt>sum)sum=cnt; 
        }
        dfs(root->left,root,cnt);
        dfs(root->right,root,cnt);

    }
    int longestConsecutive(TreeNode* root) {
        dfs(root,nullptr,1);
        return sum;
    }
};

最长连续路径的长度II

后根遍历
给定二叉树的根 root ，返回树中最长连续路径的长度。
连续路径是路径中相邻节点的值相差 1 的路径。此路径可以是增加或减少。
例如， [1,2,3,4] 和 [4,3,2,1] 都被认为有效，但路径 [1,2,4,3] 无效。
另一方面，路径可以是子-父-子顺序，不一定是父子顺序。

class Solution {
public:
    int ans=0;
    pair<int,int>dfs(TreeNode*root){
        if(!root)return {0,0};
        auto [leftup,leftdown]=dfs(root->left);
        auto [rightup,rightdown]=dfs(root->right);
        //auto {leftup,leftdown}=dfs(root->left);
        //auto {rightup,rightdown}=dfs(root->right);
        int newup=1,newdown=1;
        if(root->left&&root->val==root->left->val+1)newup=max(newup,leftup+1);
        if(root->left&&root->val==root->left->val-1)newdown=max(newdown,leftdown+1);
        if(root->right&&root->val==root->right->val+1)newup=max(newup,rightup+1);
        if(root->right&&root->val==root->right->val-1)newdown=max(newdown,rightdown+1);
        ans=max(ans,newdown+newup-1);
        return {newup,newdown};
    }
    int longestConsecutive(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

250

同值子树

后根遍历
给定一个二叉树，统计该二叉树数值相同的子树个数。同值子树是指该子树的所有节点都拥有相同的数值。

class Solution {
public:

    bool dfs(TreeNode*root,int &cnt){
        if(!root)return true;
        bool left =dfs(root->left,cnt);
        bool right=dfs(root->right,cnt);
        if(!left||!right)return false;
        if(root->left&&root->left->val!=root->val||root->right&&root->right->val!=root->val)
        return false;
        cnt++;
        return cnt;
    }

    int countUnivalSubtrees(TreeNode* root) {
        int cnt=0;
        dfs(root,cnt);
        return cnt;
    }
};

后根遍历

子树最大平均值

class Solution {
public:
    pair<int,int>dfs(TreeNode*root,double&ans){
        if(!root)return {0,0};
        auto [leftcnt,leftsum]=dfs(root->left,ans);
        auto[rightcnt,rightsum]=dfs(root->right,ans);
        int anscnt=leftcnt+rightcnt+1;
        int anssum=leftsum+rightsum+root->val;
        ans=max(ans,(double)anssum/anscnt);
        return {anscnt,anssum};
    }
    double maximumAverageSubtree(TreeNode* root) {
        double ans=0;
        dfs(root,ans);
        return ans;
    }

};

二叉树边界

class Solution {
public:
    void dfs(TreeNode*root,int flag,vector<int>&ans){
        if(!root)return;
        //无方向 寻找叶结点
        if(flag==0){
            if(!root->left&&!root->right)ans.push_back(root->val);
            dfs(root->left,0,ans);
            dfs(root->right,0,ans);
            return;
        }
        //左方向 先根遍历
        if(flag==-1){
            ans.push_back(root->val);
            if(root->left){
                dfs(root->left,flag,ans);
                dfs(root->right,0,ans);
            }
            else{
                dfs(root->right,flag,ans);
            }
        }
        //右方向 后根遍历
        else{
            if(root->right){
                dfs(root->left,0,ans);
                dfs(root->right,flag,ans);
            }
            else{
                dfs(root->left,flag,ans);
            }
            ans.push_back(root->val);
        }
    }
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        if(!root)return {};
        vector<int>ans{root->val};
        dfs(root->left,-1,ans);
        dfs(root->right,1,ans);
        return ans;
    }
};

寻找叶子结点

不断删除直到为空 从下往上计算高度相同

class Solution {
public:
    int dfs(TreeNode*root,map<int,vector<int>>&m){
        if(!root)return 0;
        int d=1+max(dfs(root->left,m),dfs(root->right,m));
        m[d].push_back(root->val);
        return d;
    }
    vector<vector<int>> findLeaves(TreeNode* root) {
        map<int,vector<int>>m;
        vector<vector<int>>ans;
        dfs(root,m);
        for(auto &p:m)
        ans.push_back(p.second);
        return ans;
    }
};

反序列化

#include<iostream>
using namespace std;
string Inorder;
string Levelorder;
void dfs(int l1,int r1,int l2,int r2){
    int i,j;
    for(i=l2;i<=r2;i++){
       bool flag =false;    
       for(j=l1;j<=r1;j++){
          if(Levelorder[i]==Inorder[j]) {
          cout<<Levelorder[i];
          flag =true;
          break;
          }
       }
       if(flag) break;
    }
    if(j>l1)dfs(l1,j-1,l2+1,r2);
    if(j<r1)dfs(j+1,r1,l2+1,r2);
}
int main(){
    cin>>Inorder>>Levelorder;
    dfs(0,Inorder.size()-1,0,Levelorder.size()-1);
    return 0;
}