剑指offer第2版：树系列（二）

一、p182-JZ34 二叉树中和为某一值的路径

二叉树中和为某一值的路径(二)__牛客网

 回溯法本质是一个基于DFS的穷举的过程 1. 先添加值 2. 在判定现有结果是否满足条件 3. DFS 4. 回退

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>> FindPath(TreeNode* root, int target) {
        if(!root) return ret;
        dfs(root,target);
        return ret;
    }
    void dfs(TreeNode* root, int target){
        path.emplace_back(root->val);
        target-=root->val;
        if(!root->left&&!root->right&&!target) ret.emplace_back(path);
        else{
        if(root->left) dfs(root->left,target);
        if(root->right) dfs(root->right,target);
        }
        path.pop_back();
       //target+=root->val;
    }
};

 二、扩展p182-JZ34 二叉树中和为某一值的路径（任意路径）

二叉树中和为某一值的路径(三)_牛客题霸_牛客网

         既然要找所有路径上节点和等于目标值的路径个数，那我们肯定先找这样的路径起点啊，但是我们不知道起点究竟在哪里，而且任意节点都有可能是起点，那我们就前序遍历二叉树的所有节点，每个节点都可以作为一次起点，即子树的根节点。 

       查找路径的时候呢，也需要往下遍历，因此还可以继续前序遍历该子树，在遍历的过程遇到一个节点，sum相应减少，sum==0，则找到一种情况。 但是因为该题的值有正有负 所以不能直接退出，而是要接着去他的左子树和右子树看看！！

class Solution {
  public:
    int ret = 0; //用来统计路径的个数
    void dfs(TreeNode* root, int sum) {
        if (!root) return;
        sum-=root->val;
        if (sum==0) ++ret; //这个时候不能退出 因为该题有正有负 后面可能还有
        //接下来去看看做子树和右子树
        dfs(root->left,sum);
        dfs(root->right,sum);
    }
    int FindPath(TreeNode* root, int sum) {
        if (!root) return 0;
        //以该点为根节点
        dfs(root, sum);
        //分别以他们的左右子树为跟节点
        FindPath(root->left, sum);
        FindPath(root->right, sum);
        return ret;
    }
};

三、p191-JZ36 二叉搜索树与双向链表

 二叉搜索树与双向链表_牛客题霸_牛客网

 ​​​​​​

class Solution {
  public:
    void Inorder(TreeNode* cur, TreeNode*& prev) {
        if (!cur) return;
        Inorder(cur->left, prev);
        //可以开始处理了
        cur->left = prev;
        if (prev) prev->right = cur;
        prev = cur;
        Inorder(cur->right, prev);
    }
//我们可以用一个prev指针来标记前一个遍历的节点  这样可以进行连接
//可以右指针怎么修改呢？？我还没遍历到后面呢！
//但是我们知道cur一定是前一个节点的右指针
//所以我们可以在一个步骤里自己的左指针指向前驱，然后让前驱的右指针指向自己
    TreeNode* Convert(TreeNode* root) {
        if (!root) return nullptr;
        TreeNode* prev = nullptr;
        Inorder(root, prev);
        while (root->left) root = root->left; //向左一直找到链表头
        return root;
    }
};

 四、p194-JZ37 序列化二叉树(重点！)

序列化二叉树_牛客题霸_牛客网

         根据重建二叉树，我们知道可以从前序遍历序列和中序遍历序列中构建一颗二叉树，受此启发，我们可以先把一个二叉树序列化成一个前序序列和中序序列，然后在反序列化时通过两个序列重构出原二叉树。但是这个思路有两个缺点：1、必须要求二叉树中不能有数值重复的点。2、只有当两个序列的所有数据都读出来了才能够进行反序列化，如果两个序列的数据是从一个流里读出来的（没有并行），那么这个过程会花费很多时间！！

思路1：实际上如果二叉树的序列化是从根开始的，那么反序列化在根节点的数值读出来的时候就可以开始了，因此我们可以使用前序遍历来序列化二叉树！！

#include <string>
class Solution {
public:
    void SerializeHelper(TreeNode *root,string&s){
         if(root==nullptr) {
            s+='#';
            return;
         }
         //根节点
         s+=to_string(root->val)+',';//用,做分隔符
         //然后去左子树和右子树处理
         SerializeHelper(root->left,s);
         SerializeHelper(root->right,s);
    }
    char* Serialize(TreeNode *root) {    
        if(!root) return nullptr; 
        string s;
        SerializeHelper(root,s);//利用他来帮助我们递归序列化
        //然后把s换成char*类型
        char*ret=new char[s.size()+1];//算上'\0'
        strcpy(ret,s.c_str());
        ret[s.size()]='\0';
        return ret;
    }
    TreeNode* Deserialize(char *&str) {
        if(str==nullptr||*str=='\0') return nullptr;
        if(*str=='#') {
        ++str;//向后遍历看看
        return nullptr;
        }
        int val=0;
        while(*str!=','&&*str!='\0'){
            val=val*10+(*str-'0');
            ++str;
        }
        //此时可以构建一个节点了
        auto* root = new TreeNode(val);
         ++str;
        //然后进行连接
        root->left=Deserialize(str);
        root->right=Deserialize(str);
        return root;
    }
};

 思路2：根据题目给我们的提示，进行层序遍历！！

     我们使用999 作为无效值（当然也可以不使用数字，使用某个特殊字符进行表示，只要能在反序列时有所区分即可），并建立占位节点 emptyNode 用来代指空节点（emptyNode.val = 999）

class Solution {
public:
//通过层序遍历来进行序列化
    //搞一个节点来标记空节点
    TreeNode* emptynode=new TreeNode(999);
     char* Serialize(TreeNode *root) {    
        if(!root) return nullptr;//用这个符号表示当前为空
        queue<TreeNode*> q;//帮助我们进行层序遍历
        string s;
        q.push(root);
        while(!q.empty()){
            TreeNode*t=q.front();
            q.pop();
            s+=to_string(t->val)+' ';//用空格分隔
            if(t!=emptynode){
                q.push(t->left?t->left:emptynode);
                q.push(t->right?t->right:emptynode);
            }
        }
        char*ret=new char[s.size()+1];
        strcpy(ret,s.c_str());
        ret[s.size()]='\0';
        return ret;
    }
    TreeNode* Deserialize(char *str) {
        if(str==nullptr)return nullptr;
        //根据分隔符进行分割
        stringstream is(str);//写到流里面
        string s;
        vector<int> v;
        while(is>>s) v.emplace_back(stoi(s));//都分割放到数组里面
        //while(getline(is,s,' ')) v.emplace_back(stoi(s));
        int n=v.size();
        //先将root节点构建出来
        auto root=new TreeNode(v[0]);
        queue<TreeNode*> q;//队列
        q.push(root);
        for(int i=1;i<n-1;i+=2){
            TreeNode*t=q.front();
            q.pop();
            if(v[i]!=999){
                auto left=new TreeNode(v[i]);
                t->left=left;
                q.push(left);
            }
            if(v[i+1]!=999){
                auto right=new TreeNode(v[i+1]);
                t->right=right;
                q.push(right);
            }
        }
        return root;
    }
};

     要注意借助stringstream流来帮助我们切割字符串 如果是空格可以直接用流，如果是其他符号可以借助getline

五、p269-JZ54 二叉搜索树的第k个节点

二叉搜索树的第k个节点_牛客题霸_牛客网

思路1：中序遍历时到达第k个元素(二叉搜索树，不存在两个相同的节点值) 

class Solution {
public:
    int ret;
    void dfs(TreeNode* root, int&k){
        if(root==nullptr||k<=0) return;
        dfs(root->left,k);
        if(--k==0) {
            ret=root->val;
            return;
        }
        dfs(root->right,k);
    }
    int KthNode(TreeNode* root, int k) {
        if(root==nullptr||k==0) return -1;
       //用中序遍历去数
       dfs(root,k);
       return k<=0?ret:-1;
    }
};

思路2：利用栈，采用循环中序遍历的方式 (参照非递归遍历二叉树)

class Solution {
  public:
    int KthNode(TreeNode* root, int k) {
        if (!root || k <= 0) return -1;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur || !st.empty()) {
            while (cur) { //将左子树全部入栈
                st.push(cur);
                cur = cur->left;
            }
                cur = st.top();
                st.pop();
                if (--k==0) return cur->val; //找到了该节点
                cur = cur->right;
        }
        return -1;
    }
};

六、p271-JZ55 二叉搜索树的深度 

二叉树的深度_牛客题霸_牛客网

 思路1：使用递归方式  后序遍历

class Solution {
public:
    int TreeDepth(TreeNode* root) {
	   if(!root) return 0;
       return 1+max(TreeDepth(root->left),TreeDepth(root->right));
    }
};

思路2：用一个变量去统计深度 然后再用一个max去找最深

class Solution {
public:
    void TreeDepthHelp(TreeNode* root,int cur,int&max){
		if(!root){
			if(max<cur) max=cur;
			return;
		}
		//去左右子树看看
		TreeDepthHelp(root->left,cur+1,max);
		TreeDepthHelp(root->right,cur+1,max);
	}
    int TreeDepth(TreeNode* root) {
	   if(!root) return 0;
       int depth=0,max=0;
	   TreeDepthHelp(root,depth,max);
	   return max;
    }
};

七、扩展p273-JZ55 判断该树是不是平衡二叉树(后序遍历)

判断是不是平衡二叉树_牛客题霸_牛客网

 左右子树高度差不超过1，且左右子树都是平衡二叉树

class Solution {
public:
    int deep(TreeNode* root){//统计子树的高度
        if(!root) return 0;
        return 1+max(deep(root->left),deep(root->right));
    }
    bool IsBalanced_Solution(TreeNode* root) {
       if(!root) return true;
       int left=deep(root->left);
       int right=deep(root->right);
       if(left-right<-1||left-right>1) return false;
       //左右子树必须是平衡的
       return IsBalanced_Solution(root->left)&&IsBalanced_Solution(root->right);
    }
};

这个代码虽然简洁。但是一个节点需要判断多次 ,所以我们用后序遍历的方式遍历二叉树的每个节点，那么再遍历这个节点之前我们已经变了了它的左右子树，因此只要在遍历的时候记录他的深度，就可以一边遍历一般判断是不是平衡的了！！

class Solution {
public:
    bool IsBalanced(TreeNode* root,int &depth){
        if(!root) return true;
        int left=0,right=0;
        //后序遍历
        if(IsBalanced(root->left,left)&&IsBalanced(root->right,right)){
            int diff=left-right;
            if(diff<=1&&diff>=-1){
                depth=1+max(left,right);
                return true;
            }
        }
        return false;
    }
    bool IsBalanced_Solution(TreeNode* root) {
        int depth=0;
        return IsBalanced(root,depth);
    }
};

八、p327-JZ68 二叉搜索树的最近公共祖先

二叉搜索树的最近公共祖先_牛客题霸_牛客网

       二叉搜索树是排序过的，位于做子树的节点都比父节点小，而位于右子树的节点都比父节点大，我们只需要从树的根节点开始和两个输入的节点进行比较，如果当前节点的值比两个节点的值都大，那么最低的公共祖先一定在当前节点的左子树中，如果都比两个节点的值小，那么就一定在他的右子树中，如果一个大一个小，那就说明当前当前节点一定是结果！！

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
      while(root){
        if(root->val>p&&root->val>q) root=root->left;
        else if(root->val<p&&root->val<q) root=root->right;
        else break;
      }
      return root->val;
    }
};

九、扩展p327-JZ68 二叉树的最近公共祖先（重点）

在二叉树中找到两个节点的最近公共祖先_牛客题霸_牛客网

      这样写的话是前序遍历，每次都要重复遍历很多点，复杂度太高了（如果遇到歪脖子树，那复杂都就是N^2） 

class Solution {
public:
    bool isintree(TreeNode* root,int x){
        if(!root) return false;
        return root->val==x||isintree(root->left,x)||isintree(root->right,x);
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
       if(root->val==o1||root->val==o2) return root->val;//如果p和q其中一个为根
       //然后此时我要去我的左子树和右子树找一找这两个点
        //此时就要去看看我的左子树和右子树找一找
        bool pleft=isintree(root->left,o1);
        bool pright=!pleft;
        bool qleft=isintree(root->left,o2);
        bool qright=!qleft;
        if(pleft&&qright||qleft&&pright) return root->val;
        else if(pleft&&qleft) return lowestCommonAncestor(root->left,o1,o2);
        else return lowestCommonAncestor(root->right,o1,o2);
    }
};

根据启发思路2，如果我们有父节点 就可以转化成相交链表的问题，那么既然我们不能通过父节点回溯，那么就可以通过容器来将遍历过的节点存起来！！

class Solution {
public:
    bool dfs(TreeNode* root,int x,stack<int>&path){//因为不确定压入节点是否是对的，所以要用bool类型的返回值
        if(!root) return false;//为空就不找了
        path.push(root->val);//先入栈 然后去左边和右边找一下
        if(root->val==x||dfs(root->left,x,path)||dfs(root->right,x,path)) return true;
        //都不是 就回溯
        path.pop();
        return false;
    }
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
      if(root->val==p||root->val==q) return root->val;
      //定义两个容器来帮我们存储遍历过的节点
      stack<int> pPath,qPath;
      dfs(root,p,pPath);
      dfs(root,q,qPath);
      //此时两个栈就存好了 然后进行公共节点的查找
      while(pPath.size()!=qPath.size()){
        if(pPath.size()>qPath.size()) pPath.pop();
        else qPath.pop();
      }
      //此时两个一起弹 直到遇到相同的
      while(pPath.top()!=qPath.top()){
        pPath.pop();
        qPath.pop();
      }
      return pPath.top();
    }
};

思路3：如果我们两个一起找，只要存在一个就返回对应的点（后序遍历）

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
      if(!root) return 0;//0表示没找到
      if(root->val==o1||root->val==o2) return root->val;//说明找到了
      //此时两个一起找
      int left=lowestCommonAncestor(root->left, o1, o2);
      int right =lowestCommonAncestor(root->right, o1, o2);
      if(!left) return right;//左子树没有就去右子树
      if(!right) return left;//右子树没有就去左子树
      return root->val;
    }
};

时间复杂度是o（n） 因为每个节点只会遍历一次

空间复杂度是O（n）最坏的情况退化到链表