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

一、p62-重建二叉树

重建二叉树_牛客题霸_牛客网

我们可以通过前序遍历来定位根，然后去中序遍历里面找根，然后他左边的数字就是他的左子树，右边的数字就是他的右子树，然后再转化成子问题

class Solution {public:TreeNode* buildtree(vector<int>& preOrder, vector<int>& vinOrder, int& pi,int begin, int end) {if (begin > end) return nullptr;TreeNode* root = new TreeNode(preOrder[pi]);//先在中序数组中找到根int rooti = begin;while (rooti <= end) {if (vinOrder[rooti] == preOrder[pi]) break;++rooti;}//此时rooti指向的位置一定是中序的根++pi;root->left = buildtree(preOrder, vinOrder, pi, begin, rooti - 1);root->right = buildtree(preOrder, vinOrder, pi, rooti + 1, end);return root;}TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {if (preOrder.empty() || vinOrder.empty() || preOrder.size() != vinOrder.size())return nullptr;int pi = 0; //pi帮我们遍历根数组return buildtree(preOrder, vinOrder, pi, 0, vinOrder.size() - 1);}
};

二、p65-二叉树的下一个节点

二叉树的下一个结点_牛客题霸_牛客网

1/如果这个节点有右子树，那么下一个节点就是他的右子树的最左节点b->h

2/如果这个节点没有右子树，且又是父节点的左子树,那下一个就是父节点h->e

3/如果这个节点没有右子树，且又是父节点的右子树,那么就得向上找到第一个是他父节点的左子树的节点l->a （如果该过程没找到，说明该节点已经是最后一个了，返回nullptr）

class Solution {
public:TreeLinkNode* GetNext(TreeLinkNode* pNode) {
//1/如果这个节点有右子树，那么下一个节点就是他的右子树的最左节点b->h
//2/如果这个节点没有右子树，且又是父节点的左子树,那下一个就是父节点h->e
//3/如果这个节点没有右子树，且又是父节点的右子树,那么就得向上找到第一个是他父节点的左子树的节点l->aif(pNode->right){//如果有右子树  去找他右子树的最左节点pNode=pNode->right;while(pNode->left) pNode=pNode->left;return pNode;}//走到这 说明这个节点没有右子树//如果也没有父亲，说明已经走到头了 返回空if(!pNode->next) return nullptr;//如果有父亲//如果他是父亲的左子树 就直接返回父亲节点if(pNode->next->left==pNode) return pNode->next; //如果他是父亲的右子树 向上找到第一个是他父节点的左子树的节点while(pNode->next&&pNode->next->left!=pNode)  pNode=pNode->next;//如果是找不到导致的问题，那么就是nullptrif(pNode->next->left!=pNode) return nullptr;//考虑右单支树的情况return  pNode->next;}
};

三、p148-树的子结构

树的子结构_牛客题霸_牛客网

子结构怎么理解，可以理解成子结构是原树的子树(或者一部分)

我们可以分2步：第一步在树A中找到和树B相同的根节点R，第二步再以R为根节点去看看是否包含和B树一样的结构。如果不符合的话，在回到树A中去看看他的左右子树。

class Solution {
public:bool issametree(TreeNode* root, TreeNode* root_sub){if(!root_sub) return true; //此时说明比完了if(!root||root->val!=root_sub->val) return false; //隐含的条件是root_sub!=nullptr//能走下来 就去比较左右子树return issametree(root->left,root_sub->left)&&issametree(root->right,root_sub->right);}bool HasSubtree(TreeNode* root1, TreeNode* root2) {if(!root1||!root2) return false;//约定了空树不是子结构//我先看看比较一下头部 如果头相等 我就以他为基点比较if(root1->val==root2->val&&issametree(root1,root2))return true;//此时说明root1!=root2 或者是 root1和root2不一样  不管怎样都要换个起始位置if(HasSubtree(root1->left,root2)||HasSubtree(root1->right,root2)) return true;return false;}
};

四、p157-二叉树的镜像

二叉树的镜像_牛客题霸_牛客网

所谓的二叉树镜像本质是自顶向下(or自底向上)进行左右子树交换的过程

class Solution {
public:TreeNode* Mirror(TreeNode* pRoot) {//交换一下自己的左右子树  然后再递归让自己的左右子树去交换if(pRoot==nullptr) return nullptr;swap(pRoot->left,pRoot->right);Mirror(pRoot->left);Mirror(pRoot->right);return pRoot;}
};

五、p159-对称的二叉树

对称的二叉树__牛客网

本质就是需要比较一下两颗树左子树和右子树是否相等

class Solution {
public:bool dfs(TreeNode* root1,TreeNode* root2){if(!root1&&!root2) return true;//走到这说明不可能两个同时为空if(!root1||!root2) return false;//走到这肯定两个都不为空了if(root1->val!=root2->val) return false;//走到这说明两个相等  这时候就去比较左子树和右子树return dfs(root1->left,root2->right)&&dfs(root1->right,root2->left);}bool isSymmetrical(TreeNode* pRoot) {//堆成其实就是双方的左孩子和右孩子相等return dfs(pRoot,pRoot);}
};

六、p171-不分行从上到下打印二叉树

从上往下打印二叉树_牛客题霸_牛客网

class Solution {
public:vector<int> PrintFromTopToBottom(TreeNode* root) {if(!root) return {};//开始层序遍历queue<TreeNode*> q;vector<int> ret;q.push(root);while(!q.empty()){//先取出要弹出的节点TreeNode* t=q.front();q.pop();ret.emplace_back(t->val);//然后让他的左右子树入队列if(t->left)  q.push(t->left);if(t->right) q.push(t->right);}return ret;}
};

七、p174-分行从上到下打印二叉树

把二叉树打印成多行_牛客题霸_牛客网

按行的话每while一次都要根据节点数来出队列

class Solution {
public:vector<vector<int>> Print(TreeNode* root) {vector<vector<int>> ret;if(!root) return ret;queue<TreeNode*> q;vector<int> path;//存储结果q.push(root);while(!q.empty()){int size=q.size();for(int i=0;i<size;++i){TreeNode* t=q.front();q.pop();path.emplace_back(t->val);if(t->left) q.push(t->left);if(t->right) q.push(t->right);}ret.emplace_back(path);path.clear();}return ret;}
};

八、p176-之字形打印二叉树

按之字形顺序打印二叉树__牛客网

其实可以按照上一题那样做然后对偶数层进行逆置数组即可。这个代码就不写了。我们换一种思路，来解决问题-——双栈

//首先我们要将第1层入栈我们会发现第2层要访问3 2 因此要按照2 3的顺序入栈然后下一层访问的4 5 ，4要先打印，所以要按照5 4的顺序入栈也就是先右子树再左子树

因此我们可以总结出规律，如果是奇数层，就要在打印的时候先保存左节点在保存右节点到第一个栈里，如果是偶数层，就要先保存右节点再保存左节点到第二个栈里

class Solution {
public:vector<vector<int>> Print(TreeNode* root) {vector<vector<int>> ret;if(!root) return ret;stack<TreeNode*> oddst;//奇数行栈stack<TreeNode*> evenst;//偶数行栈vector<int> path;//保存中间结果oddst.push(root);while(!oddst.empty()||!evenst.empty()){while(!oddst.empty()){TreeNode* t=oddst.top();oddst.pop();path.emplace_back(t->val);if(t->left) evenst.push(t->left);if(t->right) evenst.push(t->right);}if(!path.empty()){ret.emplace_back(path);path.clear();}while(!evenst.empty()){//偶数栈要先处理右子树TreeNode* t=evenst.top();evenst.pop();path.emplace_back(t->val);if(t->right)oddst.push(t->right);if(t->left) oddst.push(t->left);}if(!path.empty()){ret.emplace_back(path);path.clear();}}return ret;}
};

九、p179-二叉搜索树的后序遍历序列

二叉搜索树的后序遍历序列_牛客题霸_牛客网

对于一个序列S，最后一个元素是x （也就是root节点），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列

class Solution {
public:bool dfs(vector<int>&nums,int begin,int end){//判断区间内 if(begin>=end) return true;//说明一直没有问题int root=nums[end];//拿到根节点int i=begin;while(i<end&&nums[i]<root) ++i;//此时i位置指向的就是第一个比root大的节点for(int j=i;j<end;++j) //检测一下后面是不是都比root大if(nums[j]<root) return false;//此时说明都符合了 那就要去判断一下左区间和右区间return dfs(nums,begin,i-1)&&dfs(nums,i,end-1);}bool VerifySquenceOfBST(vector<int> nums) {//二叉搜索树 左子树一定是比根小 右子树一定比根大  if(nums.empty()) return false;//右边的是根  然后向前找到第一个比根小的  //然后遍历判断一下左边的是否都比他小  右边是不是都比他大 return dfs(nums,0,nums.size()-1); }
};