• 二叉树前序、中序、后序遍历（递归法、迭代法）

    前序遍历：（练习题）

    迭代法一：

    1. int TreeSize(struct TreeNode* root){
    2.     return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
    3. }
    4.  
    5.  
    6. int* preorderTraversal(struct TreeNode* root, int* returnSize){
    7.     if(root==NULL){
    8.         *returnSize = 0;
    9.         return (int*)malloc(sizeof(int)*0);
    10.     }
    11.     int size = TreeSize(root);//获得树的节点数
    12.     int* ans = (int*)malloc(sizeof(int)*size);//开辟数组
    13.     struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈
    14.     int top = 0;
    15.     int i = 0;
    16.     struct TreeNode* node = root;
    17.     while(i
    18.         if(node){
    19.             ans[i++] = node->val;
    20.             s[top++] = node;
    21.             node = node->left;
    22.         }else{
    23.            node = s[--top];
    24.            node = node->right; 
    25.         }
    26.     }
    27.     free(s);//释放内存
    28.     *returnSize = size;
    29.     return ans;
    30. }

    迭代法二：

    1.  
    2. int TreeSize(struct TreeNode* root){
    3.     return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
    4. }
    5.  
    6. int* preorderTraversal(struct TreeNode* root, int* returnSize){
    7.     if(root==NULL){
    8.         *returnSize = 0;
    9.         return (int*)malloc(sizeof(int)*0);
    10.     }
    11.     int size = TreeSize(root);//获得树的节点数
    12.     int* ans = (int*)malloc(sizeof(int)*size);//开辟数组
    13.     struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈
    14.     int top = 0;
    15.     int i = 0;
    16.     s[top++] = root;
    17.     while(i
    18.         struct TreeNode* node = s[--top];//出栈
    19.         if(node){
    20.             if(node->right) s[top++] = node->right;
    21.             if(node->left) s[top++] = node->left;
    22.             s[top++] = node;
    23.             s[top++] = NULL;//表明前一个根节点已经访问过子树
    24.         }else{
    25.             ans[i++] = s[--top]->val;
    26.         }
    27.  
    28.     }
    29.     free(s);//释放内存
    30.     *returnSize = size;
    31.     return ans;
    32. }
    33.

    迭代法三：

    1. int TreeSize(struct TreeNode* root){
    2.     return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
    3. }
    4.  
    5. int* preorderTraversal(struct TreeNode* root, int* returnSize){
    6.     int size = TreeSize(root);//获得树的节点数
    7.     int* ans = (int*)malloc(sizeof(int)*size);//开辟数组
    8.     struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size);//模拟栈
    9.     int top = 0;
    10.     int i = 0;
    11.     s[top++] = root;
    12.     while(i
    13.         struct TreeNode* node = s[--top];//出栈
    14.         ans[i++] = node->val;
    15.         //左右子树入栈
    16.         //根左右（栈先进后出，先入右子树后入左子树）
    17.         if(node->right)  s[top++] = node->right;
    18.         if(node->left)  s[top++] = node->left;
    19.  
    20.     }
    21.     free(s);//释放内存
    22.     *returnSize = size;
    23.     return ans;
    24. }

    递归法：

    1. void preorder(struct TreeNode* root,int* ans,int* i){
    2.     if(root==NULL) return ;
    3.     ans[(*i)++] = root->val;
    4.     preorder(root->left,ans,i);
    5.     preorder(root->right,ans,i);
    6. }
    7.  
    8. int* preorderTraversal(struct TreeNode* root, int* returnSize){
    9.     int* ans = (int*)malloc(sizeof(int)*101);
    10.     int i= 0;
    11.     preorder(root,ans,&i);
    12.     *returnSize = i;
    13.     return ans;
    14. }

    中序遍历：（练习题）

    迭代法一：

    1.  
    2. int TreeSize(struct TreeNode* root){
    3.     return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
    4. }
    5.  
    6. int* inorderTraversal(struct TreeNode* root, int* returnSize){
    7.     if(root==NULL){
    8.         *returnSize=0;
    9.         return (int*)malloc(sizeof(int)*0);
    10.     }
    11.     int size = TreeSize(root);
    12.     *returnSize = size;
    13.     int* ans = (int*)malloc(sizeof(int)*size);
    14.     struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈
    15.     int i = 0;
    16.     int top = 0;//栈顶
    17.     s[top++] = root;
    18.     while(i
    19.         struct TreeNode* node = s[--top];
    20.         if(node){
    21.             if(node->right) s[top++] = node->right;
    22.             s[top++] = node;
    23.             s[top++] = NULL;
    24.             if(node->left) s[top++] = node->left;
    25.         }else{
    26.             ans[i++] = s[--top]->val;
    27.         }
    28.     }
    29.     free(s);
    30.     return ans;
    31. }

    迭代法二：

    1. //节点个数
    2. int TreeSize(struct TreeNode* root){
    3.     return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
    4. }
    5.  
    6. int* inorderTraversal(struct TreeNode* root, int* returnSize){
    7.     if(!root){//空树
    8.         *returnSize = 0;
    9.         return (int*)malloc(sizeof(int*)*0);
    10.     }
    11.     int size = TreeSize(root);
    12.     *returnSize = size;
    13.     int* ans = (int*) malloc(sizeof(int)*size);
    14.     struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈
    15.     int i = 0;
    16.     int top = 0;//栈顶
    17.     struct TreeNode* node = root;
    18.     while(i
    19.         if(node){//一直检索左孩子
    20.             s[top++] = node;//入栈
    21.             node = node->left;//一路向左
    22.         }else{//出栈
    23.             node = s[--top];//栈顶元素出栈
    24.             ans[i++] = node->val;
    25.             node = node->right;//右子树
    26.         }
    27.     }
    28.     free(s);
    29.     return ans;
    30. }

    递归法：

    1. int TreeSize(struct TreeNode* root){
    2.     return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
    3. }
    4.  
    5. void inorder(struct TreeNode* root,int* ans,int* i){
    6.     if(root==NULL) return;
    7.     inorder(root->left,ans,i);
    8.     ans[(*i)++] = root->val;
    9.     inorder(root->right,ans,i);
    10. }
    11.  
    12. int* inorderTraversal(struct TreeNode* root, int* returnSize){
    13.     int size = TreeSize(root);
    14.     int* ans = (int*)malloc(sizeof(int)*size);
    15.     int i = 0;
    16.     inorder(root,ans,&i);
    17.     *returnSize = size;
    18.     return ans;
    19. }

    后序遍历：（练习题）

    迭代法一：

    1. int TreeSize(struct TreeNode* root){
    2.     return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
    3. }
    4.  
    5.  
    6. int* postorderTraversal(struct TreeNode* root, int* returnSize){
    7.     if(root==NULL) {
    8.         *returnSize = 0;
    9.         return (int*)malloc(sizeof(int)*0);  
    10.     }
    11.     int size = TreeSize(root);//获得树的节点数
    12.     int* ans = (int*)malloc(sizeof(int)*size);//开辟数组
    13.     struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈
    14.     int top = 0;
    15.     int i = 0;
    16.     s[top++] = root;
    17.     //先根右左进栈，之后左右根出栈
    18.     //这里注意如果root本来就为空，下面则会发生越界 所以不建议while(top>0) 或者开头便判断是否为空
    19.     while(i
    20.         struct TreeNode* node = s[--top];//弹出栈顶元素 并且pop掉
    21.         if(node){//元素不为NULL
    22.             s[top++] = node;
    23.             s[top++] = NULL;//NULL标记前面根节点已经被访问
    24.             if(node->right) s[top++] = node->right;
    25.             if(node->left) s[top++] = node->left;
    26.         }else{
    27.             ans[i++] = s[--top]->val;
    28.         }
    29.         
    30.     }
    31.     free(s);//释放内存
    32.     *returnSize = size;
    33.     return ans;
    34. }

    迭代法二：

    1.  
    2. int TreeSize(struct TreeNode* root){
    3.     return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
    4. }
    5.  
    6.  
    7. int* postorderTraversal(struct TreeNode* root, int* returnSize){
    8.     if(root==NULL) {
    9.         *returnSize = 0;
    10.         return (int*)malloc(sizeof(int)*0);  
    11.     }
    12.     int size = TreeSize(root);//获得树的节点数
    13.     int* ans = (int*)malloc(sizeof(int)*size);//开辟数组
    14.     struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈
    15.     int top = 0;
    16.     int i = 0;
    17.     struct TreeNode* node = root;
    18.     struct TreeNode* r = NULL;
    19.     while(i
    20.         if(node){
    21.             s[top++] = node;
    22.             node = node->left;
    23.         }
    24.         else{
    25.             node = s[top-1];
    26.             if(node->right&&r!=node->right){//防止重复遍历右子树
    27.                 node = node->right;
    28.             }
    29.             else{
    30.                 r = s[--top];
    31.                 ans[i++] = r->val;
    32.                 node = NULL;
    33.             }
    34.         }
    35.     }
    36.     free(s);//释放内存
    37.     *returnSize = size;
    38.     return ans;
    39. }

    递归法：

    1. int TreeSize(struct TreeNode* root){
    2.     return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
    3. }
    4.  
    5. void postorder(struct TreeNode* root,int* ans,int* i){
    6.     if(root==NULL) return ;
    7.     postorder(root->left,ans,i);
    8.     postorder(root->right,ans,i);
    9.     ans[(*i)++] = root->val;
    10. }
    11.  
    12. int* postorderTraversal(struct TreeNode* root, int* returnSize){
    13.     *returnSize = TreeSize(root);
    14.     int* ans = (int*)malloc(sizeof(int)*(*returnSize));
    15.     int i = 0;
    16.     postorder(root,ans,&i);
    17.     return ans;
    18. }

  • 相关阅读:
    聊聊Tomcat架构和生命周期
    工业级POE交换机支持什么？
    MySQL 45 讲 | 14 count(*)这么慢，我该怎么办？
    visual studio 启用C++11
    Spring 源码解读（1） - Spring上下文构造方法的初始化
    goland报错：“package command-line-arguments is not a main package”解决方案
    服务器被黑该如何查找入侵痕迹以及如何防御攻击
    Linux之ASCII码表查询tools(五十九)
    简单线性回归（Simple Linear Regression）
    【机器学习】Tensorflow.js：我在浏览器中实现了迁移学习
  • 原文地址：https://blog.csdn.net/bigBbug/article/details/133466804