剑指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个节点
思路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）最坏的情况退化到链表
