[关闭]
@kakadee 2016-06-04T06:37:46.000000Z 字数 7227 阅读 1259

树

编程 算法

1. 重建二叉树

描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

代码：

  1. TreeNode* buildHelper(vector<int> &pre,vector<int> &in,int startPre,int endPre,int startIn,int endIn)
  2. {
  3.     if (startPre > endPre || startIn > endIn) return NULL;
  4.     TreeNode *root = new TreeNode(pre[startPre]);
  5.     for(int i = startIn; i <= endIn; ++i)
  6.     {
  7.         if(in[i] == root->val)
  8.         {
  9.             root->left = buildHelper(pre,in,startPre+1,startPre+i-startIn,startIn,i-1);
  10.             root->right = buildHelper(pre,in,startPre+i-startIn+1,endPre,i+1,endIn);
  11.         }
  13.     }
  14.     return root;
  15. }

2. 序列化二叉树

描述：

根据字符串创建二叉树，和根据二叉树重建字符串。

代码：

  1. string Serialize(TreeNode *root) {
  2.     string ans;
  4.     if (root == NULL) return &ans[0];
  5.     queue<TreeNode *> Q;
  6.     Q.push(root);
  7.     while (!Q.empty()) {
  8.         TreeNode *node = Q.front();
  9.         Q.pop();
  10.         if (node == NULL) ans += ",#";
  11.         else {
  12.             Q.push(node->left);
  13.             Q.push(node->right);
  14.             string tmp = to_string(node->val);
  15.             ans += "," + tmp;                           
  16.         }
  17.                         
  18.     }
  19.     return ans.substr(1);       
  20. }  
  21. TreeNode* Deserialize(char *str) {
  22.     string s = str;
  23.     if (s.size() == 0) return NULL;
  24.     vector<TreeNode*> path;
  25.     while (s != "") {
  26.         int i = 0;
  27.         while (i < s.size() && s[i] != ',') i++;
  28.         string tmp = s.substr(0, i);
  29.         if (tmp == "#") {
  30.             TreeNode* p = NULL;
  31.             path.push_back(p);
  32.                                     
  33.         }
  34.         else {
  35.             int val = atoi(tmp.c_str());
  36.             TreeNode* p = new TreeNode(val);
  37.             path.push_back(p);
  38.                                     
  39.         }
  40.         if (i >= s.size() - 1) s = "";
  41.         else s = s.substr(i + 1);                       
  42.     }
  43.     int index = 1, i = 0;
  44.     while (index < path.size()) {
  45.         if (path[i] != NULL) {
  46.         if (index < path.size()) path[i]->left = path[index++];
  47.         if (index < path.size()) path[i]->right = path[index++];                    
  48.         }
  49.         i++;    
  50.     }
  51.     return path[0];     
  52. }

3. 二叉树的深度

代码：

  1. class Solution {
  2. public:
  3.     int TreeDepth(TreeNode* pRoot) {
  4.         if(pRoot == NULL) return 0;
  6.         int left = TreeDepth(pRoot->left);
  7.         int right = TreeDepth(pRoot->right);
  8.         return max(left,right)+1;
  9.     }
  10. };

4. 平衡二叉树

描述：

任意节点的左右子树深度相差不超过1。
判断一颗二叉树是不是平衡二叉树。

代码：

  1. //后续遍历二叉树，遍历过程中求子树高度，判断是否平衡
  2. bool isBalanced(TreeNode* root,int &depth){
  3.     if(root == NULL)
  4.         return true;
  5.     int left = 0,right = 0;
  6.     if(isBalanced(root->left,left) && isBalanced(root->right,right)){
  7.         int dif = left - right;
  8.         if(dif > 1 || dif < -1) return false;
  9.         depth = max(left,right)+1;
  10.         return true;
  11.     }
  12.     else 
  13.         return false;
  14. }
  16. bool IsBalanced_Solution(TreeNode* pRoot){
  17.     int depth = 0;
  18.     return isBalanced(pRoot,depth);
  19. }

5. 二叉树的镜像

描述：

二叉树的镜像定义：
源二叉树
       8
      / \
     6 10
   / \ / \
  5 7 9 11
镜像二叉树
       8
      / \
     10 6
   / \ / \
  11 9 7 5

操作给定的二叉树，将其变换为源二叉树的镜像。

代码：

  1. void Mirror(TreeNode *pRoot){
  2.     if(pRoot == NULL)
  3.         return;
  4.     TreeNode* tmp = pRoot->left;
  5.     pRoot->left = pRoot->right;
  6.     pRoot->right = tmp;
  7.     Mirror(pRoot->left);
  8.     Mirror(pRoot->right);
  9. }

6. 对称二叉树

描述：

如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
判断一颗二叉树是不是对称的。

代码：

  1. bool cmpRoot(TreeNode* left,TreeNode* right){
  2.     if(left == NULL && right == NULL)
  3.         return true;
  4.     if((!left && right) || (!right && left))
  5.         return false;
  6.     if(left->val != right->val)
  7.         return false;
  8.     return cmpRoot(left->right,right->left) && cmpRoot(left->left,right->right);
  9. }
  10. bool isSymmetrical(TreeNode* pRoot){
  11.     if(pRoot == NULL) return true;
  12.     return cmpRoot(pRoot->left,pRoot->right);
  13. }

7. 二叉树的子结构

描述：

输入两颗二叉树A，B，判断B是不是A的子结构。
(空树不属于任何一个树的子结构）

代码：

  1. bool isSubtree(TreeNode* pRootA, TreeNode* pRootB){
  2.     if(pRootB == NULL) return true;
  3.     if(pRootA == NULL) return false;
  4.     if(pRootA->val == pRootB->val)
  5.         return isSubtree(pRootA->left,pRootB->left) && isSubtree(pRootA->right,pRootB->right);
  6.     else
  7.         return false;
  8. }
  9. bool HasSubtree(TreeNode* pRootA, TreeNode* pRootB){
  10.     if(pRootA == NULL) return false;
  11.     return isSubtree(pRootA,pRootB) || HasSubtree(pRootA->left,pRootB) || HasSubtree(pRootA->right,pRootB);
  12. }

8. 二叉树和双向链表

描述：

代码：

  1. TreeNode* Convert(TreeNode* root)
  2. {
  3.     if (root == NULL || (!root->left && !root->right))
  4.     {
  5.         return root;
  6.     }
  8.     // 先返回左子树双向链表的表头
  9.     TreeNode *left = Convert(root->left);
  11.     if (!left){
  12.         TreeNode *p = left;
  13.         while(p && p->right){
  14.             p = p->right;
  15.         }
  16.         root->left = p;
  17.         p->right = root;
  18.     }
  19.     // 再返回右子树双向链表的表头
  20.     TreeNode *right = Convert(root->right);
  21.     if (right) {
  22.         root->right = p;
  23.         p->left = root;
  24.     }
  26.     return left == NULL ? root:left;
  27. }

9. 二叉树中序遍历的下一个结点

描述：

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

代码：

  1. // 1. 如果此节点有右子树，返回右子树的最左节点
  2. // 2. 否则，如果该节点是父节点的左孩子，返回其父节点；
  3. // 3. 否则，向上找到有左孩子的父节点，返回该父节点。
  4. TreeLinkNode* GetNext(TreeLinkNode* pNode)
  5. {
  6.     if(!pNode) return NULL;
  7.     if (pNode->right)
  8.     {
  9.         TreeLinkNode* p = pNode->right;
  10.         while (p && p->left)
  11.         {
  12.             p = p->left;
  13.         }
  14.         return p;
  15.     }
  16.     while (pNode->next) {
  17.         if(pNode->next->left == pNode)
  18.             return pNode->next;
  19.         pNode = pNode->next;
  20.     }
  21.     return NULL;
  22. }

10. 前序中序二叉树求后序

代码：

  1. string post;
  2. void postprint(string pre,string in) {
  3.     if(pre.size() == 0) return;
  4.     int pos = in.find(pre[0]);
  5.     postprint(pre.substr(1,pos),in.substr(0,pos));
  6.     postprint(pre.substr(pos+1),in.substr(pos+1));
  7.     post.push_back(pre[0]);
  8. }

11. 层次遍历二叉树

代码：

  1. vector<int> PrintFromTopToBottom(TreeNode *root) {
  2.     vector<int> ans;
  3.     if (root == NULL) return ans;
  4.     queue<TreeNode *> Q;
  5.     Q.push(root);
  6.     while(!Q.empty()) {
  7.         TreeNode *node = Q.front();
  8.         Q.pop();
  9.         if(node->left) Q.push(node->left);
  10.         if(node->right) Q.push(node->right);
  11.         ans.push_back(node->val);
  12.     }
  13.     return ans;
  14. }

12. 层次遍历二叉树2

描述：

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

代码：

  1. vector<vector<int> > Print(TreeNode* root) {
  2.     vector<vector<int>> ans;
  3.     if(root == NULL) return ans;
  4.     vector<int> tmp; //存储每一个层的值
  5.     queue<TreeNode *> Q;
  6.     queue<int> level;
  7.     int curlevel = 0;
  8.     Q.push(root);
  9.     level.push(0);
  10.     while(!Q.empty()){
  11.  //如果现在队列顶端的节点level值大于curlevel,证明已经进入到下一层，所以更新curlevel到现在的层
  12.         if(level.front()>curlevel){
  13.             curlevel=level.front();
  14.             ans.push_back(tmp);
  15.             tmp.clear();
  16.         }
  17.         TreeNode *node = Q.front();
  18.         Q.pop();
  19.         level.pop();
  20. //每一次将当前节点放入tmp中，并将他的子节点放入队列，等待之后的遍历，子节点所在的level层数加一，同时放入队列
  21.         tmp.push_back(node->val); 
  22.         if(node->left){
  23.             Q.push(node->left);
  24.             level.push(curlevel+1);
  25.         }
  26.         if(node->right){
  27.             Q.push(node->right);
  28.             level.push(curlevel+1);
  29.         }
  30.     }
  31. //由于最后一次Q为空，所以最后一层存储在tmp里的值并没有放入ans中，所以得再放置一次
  32.         ans.push_back(tmp); 
  33.     return ans;
  34. }

13. 按之字形顺序打印二叉树

描述：

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

代码：

  1. vector<vector<int> > Printz(TreeNode* root)
  2. {
  3.     vector< vector<int> > ans;
  4.     if (root == NULL) return ans;
  5.     queue<TreeNode *> Q;
  6.     queue<int> level;
  7.     vector<int> tmp;
  8.     int curLevel = 0;
  9.     Q.push(root);
  10.     level.push(0);
  12.     while(!Q.empty()) {
  13.         if(level.front() > curLevel){
  15.             if(curLevel & 1) // 如果是奇数层,翻转
  16.                 reverse(tmp.begin(),tmp.end());
  17.             ans.push_back(tmp);
  18.             tmp.clear();
  20.             curLevel = level.front();
  21.         }
  22.         TreeNode *node = Q.front();
  23.         Q.pop();
  24.         level.pop();
  25.         tmp.push_back(node->val);
  26.         if(node->left){
  27.             Q.push(node->left);
  28.             level.push(curLevel+1);
  29.         }
  30.         if(node->right){
  31.             Q.push(node->right);
  32.             level.push(curLevel+1);
  33.         }
  34.     }
  35.     if(curLevel & 1)
  36.         reverse(tmp.begin(),tmp.end());
  37.     ans.push_back(tmp);
  38.     return ans;
  39. }

14. 二叉搜索树的后序遍历序列

描述：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

代码：

  1. //BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。
  3. bool judge(vector<int>& a, int left, int right) {
  4.     if (left >= right) return true;
  5.     int i = left;
  6. // 这一句特别重要，如果不判断右子树是否比根大，那么【7，4，6，5】就会错误判断
  7.     while (i < right && a[i] < a[right]) i++;
  8.     for (int j = i; j < right; j++)
  9.         if (a[j] < a[right]) return false;
  10.     return judge(a, left, i - 1) && judge(i, right - 1);
  11. }
  12. bool VerifySquenceOfBST(vector<int> a) {
  13.     if (!a.size()) return false;
  14.     return judge(a, 0, a.size() - 1);
  15. }

15. 二叉树中和为某一值的路径

描述：

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。

代码：

  1. class Solution {
  2. public:
  3.     vector<vector<int> > ans;
  4.     vector<int> path;
  5.     void helper1(TreeNode* root, int target) { // 从根节点到叶子节点和为target的路径
  6.         path.push_back(root->val);
  7.         if (target - root->val == 0 && !root->left && !root->right) {
  8.             ans.push_back(path); // 此处不应该有return，如果return 那么path.pop_back()将不执行
  9.         }
  10.         if (root->left) helper1(root->left, target - root->val);
  11.         if (root->right) helper1(root->right, target - root->val);
  12.         path.pop_back();
  13.     }
  14.     void helper2(TreeNode* root, int target) { // 从根节点到任意节点和为target的路径
  15.         path.push_back(root->val);
  16.         if (target - root->val == 0) {
  17.             ans.push_back(path);
  18.         }
  19.         if (root->left) helper2(root->left, target - root->val);
  20.         if (root->right) helper2(root->right, target - root->val);
  21.         path.pop_back();
  22.     }
  23.     void helper3(TreeNode* root, int target) { // 任意父节点到子节点和为target的路径
  24.         helper2(root, target);
  25.         if (root->left) helper3(root->left, target);
  26.         if (root->right) helper3(root->right, target);
  27.     }
  28.     vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
  29.         if (root == NULL) return ans;
  30.         helper1(root, expectNumber);
  31.         return ans;
  32.    }
  33. }; 
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注