LeetCode 树[L1 ]A篇

力扣上树的题目很多~主要运用dfs，可以好好锻炼递归水平

//本人不刷力扣的之前递归真的非常非常菜，蒟蒻而且乱递归

力扣的上递归地大量训练对俺这样的菜鸡真的太棒了👍

---

100. 相同的树

bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==NULL&&q==NULL) return true;
        if(p==NULL||q==NULL)  return false;
        if(p->val==q->val) return  isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
        else return false;
    }

---

102. 二叉树的层次遍历

层次遍历板子来喽~

vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> >vt;
        if(root==NULL)
            return  vt;
        queue<TreeNode*>q;
        q.push(root);
        while(!q.empty())
        {
            vector<int>temp;
            int len=q.size();
            while(len--)
            {
                TreeNode* top=q.front();
                q.pop();
                if(top->left!=NULL)
                    q.push(top->left);
                if(top->right!=NULL)
                    q.push(top->right);
                temp.push_back(top->val);
            }
            vt.push_back(temp);
        }
        return vt;
    }

---

101. 镜像树

bool dfs(TreeNode* p,TreeNode* q)
 {
        if(p==NULL&&q==NULL)    return true;
        else if(p==NULL||q==NULL||p->val!=q->val)
        return false;
        else 
        return dfs(p->left,q->right)&&dfs(p->right,q->left);
 }
bool isSymmetric(TreeNode* root)
{
        if(root==NULL) return true;   
        else return dfs(root->left,root->right);
 }

---

104. 二叉树的最大深度

int maxDepth(TreeNode* root) {
        if(root==NULL)
        return false;
        int maxleft=maxDepth(root->left);
        int maxright=maxDepth(root->right);
        return  max(maxleft,maxright)+1;
    }

111. 二叉树的最小深度

题中有说明：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
所以要加上一句：如果一棵子树为NULL，返回两子树和+1的深度就好了

 int minDepth(TreeNode* root) {
        if(root==NULL)
            return 0;
        int leftdepth=minDepth(root->left);
        int rightdepth=minDepth(root->right);
        if(root->left==NULL||root->right==NULL)
            return leftdepth+rightdepth+1;
        return min(leftdepth,rightdepth)+1;
    }

---

108. 将有序数组转换为二叉搜索树

其中序遍历的顺序是有序的，所以根据中序遍历的情况我们可以进行分治，注意左右区间的情况，这种类型的分治，一般采用左闭右闭取大于

• 左闭右闭

TreeNode* build(vector<int>& st,int l,int r)
    {
        if(l>r)//等号不能取
            return NULL;
        int mid=(l+r)/2;
        TreeNode* root=new TreeNode(st[mid]);
        root->left=build(st,l,mid-1);
        root->right=build(st,mid+1,r);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums,0,nums.size()-1);
    }

• 左闭右开

    TreeNode* build(vector<int>& st,int l,int r)
    {
        if(l>=r)//等号必须取到
            return NULL;
        int mid=(l+r)/2;
        TreeNode* root=new TreeNode(st[mid]);
//区间为[l,mid],[mid+1,r]
        root->left=build(st,l,mid);
        root->right=build(st,mid+1,r);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums,0,nums.size());//往后开一位
    }

• 左开右闭

TreeNode* build(vector<int>& st,int l,int r)
    {
        if(l==r)//类似
            return NULL;
        int mid=(r+l+1)/2;//左开向上取整
        TreeNode* root=new TreeNode(st[mid]);
        root->left=build(st,l,mid-1);
        root->right=build(st,mid,r);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums,-1,nums.size()-1);//向左一位
    }

---

257. 二叉树的所有路径

• 借用评论区dalao的一句话补充一下赋值传值的知识

思路：本题需要注意string的用法，要注意对于string而言，我们采用的赋值传值的方式（不是引用或者指针），这样就意味着每次调用这个函数就会创建一个新的string，并且还会在调用的时候把上一个string的值传给它，这样就意味着每个函数中的path均不相同，对于vector我们采用引用传值的方式，因为我们只需要一个即可，并且我们需要每个函数操作的要一致所以采用引用方式。

新学了效率更高的加字符串s.append("xswl");
先"A->"再递归，所以递归到边界处多加了一次" - > "，要删掉。
原来.erase()是从当前位删到尾巴为止的啊！

         path.append("->");
        if(root->left==NULL&&root->right==NULL)
        {
            path.erase(path.size()-2);
 //path.push_back(0,path.substr()-2);
            res.push_back(path);
        }
        binaryTree(root->left,path,res);
        binaryTree(root->right,path,res); 

改进后的"A"再递归("->A")

void binaryTree(TreeNode* root,string path,vector<string>&res)
    {
        if(root==NULL)  return ;
        path.append(to_string(root->val));//转化为字符串存在s中
        if(root->left==NULL&&root->right==NULL)
            res.push_back(path);
        binaryTree(root->left,path+"->",res);
        binaryTree(root->right,path+"->",res); 
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string>res;
        string path="";
        binaryTree(root,path,res);
        return res;
    }

所以就和平时输出空格差不多
第一种是"A空"，"A空"...需要删掉尾巴
第二种是"A"，"空A"，"空A"...就不用删尾巴了

---

437. 路径总和 III

这题递归边界错了，假如判断放前面，减操作放后面，当sum=0时不是直接返回该层，而是跑到左右子树，这样答案就是原来的两倍。

• 双重递归

int tol=0;
    void dfs(TreeNode* root,int sum)
    {
        if(root==NULL&&sum>0)  return ;
        if(sum<0)   return ;
        sum-=root->val;
        if(sum==0)  
        {
            tol++;
            return ;
        }
        //sum-=root->val;不能放这里
        dfs(root->left,sum);
        dfs(root->right,sum);
    }
    int pathSum(TreeNode* root, int sum) {
        if(root==NULL)  return 0;
        dfs(root,sum);
        pathSum(root->left,sum);
        pathSum(root->right,sum);
        return tol;
    }

• 前缀和递归

害搁那双重递归呢，面试官问你O(n)怎么做又不会了?

不要忘记回溯去掉标记（++与--），免得影响后面的递归。

 map<int,int>book;
    int pathSum(TreeNode* root, int sum) {
        //到根节点距离为0的路径是有的，即根节点自己
        //这句话不要遗漏了
        book[0]=1;
        return dfs(root,sum,0);
    }
    int dfs(TreeNode* root,int sum,int pre_sum)
    {
        if(root==NULL)  return 0;
        int res=0;
        pre_sum+=root->val;
        res+=book[pre_sum-sum];//前缀和之差有这个节点的化
//此处写为book[]=1就错了，因为可以一条路径上多条所需路径
        book[pre_sum]++;
        res+=(dfs(root->left,sum,pre_sum)+dfs(root->right,sum,pre_sum));
        book[pre_sum]--;
        return res;
    }

---

501. 二叉搜索树中的众数

先用中序遍历保存BST的递增序列，然后再开一个vector用来保存众数，初始化的第一个众数是非空序列的第一个数，出现次数为1，最大出现次数为1，然后从第二个数开始遍历递增序列，比较当前数字和上一个数字的大小，如果和当前数字相等，就出现次数cur++，否则出现次数置cur=1；再比较当前数出现次数和最大次数比较，假如和最大次数要相等，就加入；假如比最大次数大，就清空vector，重新加入当前数。

vector<int>temp,res;
    int cur=1;
    int MAX=1;
    vector<int> findMode(TreeNode* root) {
        inorder(root);
        if(!temp.size())    return res; 
        res.push_back(temp[0]);
        for(int i=1;i<temp.size();i++)
        {
            if(temp[i]==temp[i-1])  cur++;
            else cur=1;
            if(cur==MAX)
                res.push_back(temp[i]);
            else if(cur>MAX)
            {
                MAX=cur;
                res.clear();
                res.push_back(temp[i]);
            }
        }
        return res;
    }
    void inorder(TreeNode* root)
    {
        if(root==NULL)  return ;
        inorder(root->left);
        temp.push_back(root->val);
        inorder(root->right);
    }

---

538. 把二叉搜索树转换为累加树

中序遍历改为先右后左，然后递归回来的时候累加结点，sum传引用

 TreeNode* convertBST(TreeNode* root) {
        int sum=0;
        inorder(root,sum);
        return root;
    }
    void inorder(TreeNode *root,int &sum)
    {
        if(root==NULL)  return;
        inorder(root->right,sum);
        sum+=root->val;
        root->val=sum;
        inorder(root->left,sum);
    }

---

543. 二叉树的直径

递归左子树
递归右子树
当前结点最长直径为 MAX=max(MAX,leftheight+rightheight)
返回左右子树中长的那条再加高度 max(leftheight,rightheight)+1;

int MAX=0;
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return MAX;
    }
    int dfs(TreeNode* root)
    {
        if(root==NULL)  return 0;
        int leftheight=dfs(root->left);
        int rightheight=dfs(root->right);
        MAX=max(leftheight+rightheight,MAX);
        return max(leftheight,rightheight)+1;
    }

---