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

前序遍历：（练习题）

迭代法一：

int TreeSize(struct TreeNode* root){return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}int* preorderTraversal(struct TreeNode* root, int* returnSize){if(root==NULL){*returnSize = 0;return (int*)malloc(sizeof(int)*0);}int size = TreeSize(root);//获得树的节点数int* ans = (int*)malloc(sizeof(int)*size);//开辟数组struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈int top = 0;int i = 0;s[top++] = root;while(i<size){struct TreeNode* node = s[--top];//出栈if(node){if(node->right) s[top++] = node->right;if(node->left) s[top++] = node->left;s[top++] = node;s[top++] = NULL;//表明前一个根节点已经访问过子树}else{ans[i++] = s[--top]->val;}}free(s);//释放内存*returnSize = size;return ans;
}

迭代法二：

int TreeSize(struct TreeNode* root){return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}int* preorderTraversal(struct TreeNode* root, int* returnSize){int size = TreeSize(root);//获得树的节点数int* ans = (int*)malloc(sizeof(int)*size);//开辟数组struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size);//模拟栈int top = 0;int i = 0;s[top++] = root;while(i<size){struct TreeNode* node = s[--top];//出栈ans[i++] = node->val;//左右子树入栈//根左右（栈先进后出，先入右子树后入左子树）if(node->right)  s[top++] = node->right;if(node->left)  s[top++] = node->left;}free(s);//释放内存*returnSize = size;return ans;
}

递归法：

void preorder(struct TreeNode* root,int* ans,int* i){if(root==NULL) return ;ans[(*i)++] = root->val;preorder(root->left,ans,i);preorder(root->right,ans,i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize){int* ans = (int*)malloc(sizeof(int)*101);int i= 0;preorder(root,ans,&i);*returnSize = i;return ans;
}

中序遍历：（练习题）

迭代法：

int TreeSize(struct TreeNode* root){return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}int* inorderTraversal(struct TreeNode* root, int* returnSize){if(root==NULL){*returnSize=0;return (int*)malloc(sizeof(int)*0);}int size = TreeSize(root);*returnSize = size;int* ans = (int*)malloc(sizeof(int)*size);struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈int i = 0;int top = 0;//栈顶s[top++] = root;while(i<size){struct TreeNode* node = s[--top];if(node){if(node->right) s[top++] = node->right;s[top++] = node;s[top++] = NULL;if(node->left) s[top++] = node->left;}else{ans[i++] = s[--top]->val;}}free(s);return ans;
}

递归法：

int TreeSize(struct TreeNode* root){return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}void inorder(struct TreeNode* root,int* ans,int* i){if(root==NULL) return;inorder(root->left,ans,i);ans[(*i)++] = root->val;inorder(root->right,ans,i);
}int* inorderTraversal(struct TreeNode* root, int* returnSize){int size = TreeSize(root);int* ans = (int*)malloc(sizeof(int)*size);int i = 0;inorder(root,ans,&i);*returnSize = size;return ans;
}

后序遍历：（练习题）

迭代法：

int TreeSize(struct TreeNode* root){return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}int* postorderTraversal(struct TreeNode* root, int* returnSize){if(root==NULL) {*returnSize = 0;return (int*)malloc(sizeof(int)*0);  }int size = TreeSize(root);//获得树的节点数int* ans = (int*)malloc(sizeof(int)*size);//开辟数组struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈int top = 0;int i = 0;s[top++] = root;//先根右左进栈，之后左右根出栈//这里注意如果root本来就为空，下面则会发生越界 所以不建议while(top>0) 或者开头便判断是否为空while(i<size){struct TreeNode* node = s[--top];//弹出栈顶元素 并且pop掉if(node){//元素不为NULLs[top++] = node;s[top++] = NULL;//NULL标记前面根节点已经被访问if(node->right) s[top++] = node->right;if(node->left) s[top++] = node->left;}else{ans[i++] = s[--top]->val;}}free(s);//释放内存*returnSize = size;return ans;
}

递归法：

int TreeSize(struct TreeNode* root){return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}void postorder(struct TreeNode* root,int* ans,int* i){if(root==NULL) return ;postorder(root->left,ans,i);postorder(root->right,ans,i);ans[(*i)++] = root->val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize){*returnSize = TreeSize(root);int* ans = (int*)malloc(sizeof(int)*(*returnSize));int i = 0;postorder(root,ans,&i);return ans;
}