文章目录
原题题目
代码实现（首刷自解）
代码实现（二刷Morris）
代码实现（迭代）
代码实现（三刷DAY 85 递归）
代码实现（四刷DAY 134 递归）
代码实现（四刷C++ DAY134 迭代）
代码实现（五刷自解 DAY 225 C++）
代码实现（六刷自解 DAY 274 C++）
代码实现（七刷自解 DAY 4 Golang）
原题题目
代码实现（首刷自解）
# define MAX 101 void visit ( struct TreeNode * root, int * returnSize, int * arr)
{
if ( root) {
visit ( root-> left, returnSize, arr) ; arr[ ( * returnSize) ++ ] = root-> val; visit ( root-> right, returnSize, arr) ; }
} int * inorderTraversal ( struct TreeNode * root, int * returnSize) {
int * arr = ( int * ) malloc ( sizeof ( int ) * MAX) ; ( * returnSize) = 0 ; visit ( root, returnSize, arr) ; return arr;
}
代码实现（二刷Morris）
# define MAX 101 int * inorderTraversal ( struct TreeNode * root, int * returnSize) {
int * arr = ( int * ) malloc ( sizeof ( int ) * MAX) ; ( * returnSize) = 0 ; struct TreeNode * position; while ( root) {
position = root-> left; if ( ! position) {
arr[ ( * returnSize) ++ ] = root-> val; root = root-> right; } else {
while ( position-> right != root && position-> right) position = position-> right; if ( ! position-> right) {
position-> right = root; root = root-> left; } else {
position-> right = NULL ; arr[ ( * returnSize) ++ ] = root-> val; root = root-> right; } } } return arr;
}
代码实现（迭代）
# define MAX 101 int * inorderTraversal ( struct TreeNode * root, int * returnSize) {
int * arr = ( int * ) malloc ( sizeof ( int ) * MAX) , size = 0 ; ( * returnSize) = 0 ; struct TreeNode * position = root, * stack[ MAX] ; while ( position != NULL || size > 0 ) {
while ( position != NULL ) {
stack[ size++ ] = position; position = position-> left; } position = stack[ -- size] ; arr[ ( * returnSize) ++ ] = position-> val; position = position-> right; } return arr;
}
代码实现（三刷DAY 85 递归）
class Solution {
public : vector< int > ret; void visit ( TreeNode* root) {
if ( ! root) return ; visit ( root-> left) ; ret. push_back ( root-> val) ; visit ( root-> right) ; return ; } vector< int > inorderTraversal ( TreeNode* root) {
visit ( root) ; return ret; }
} ;
代码实现（四刷DAY 134 递归）
class Solution {
public : TreeNode* visit ( const vector< int > & nums, int left, int right) {
if ( left > right) return nullptr ; int pos = ( left+ right) / 2 ; auto root = new TreeNode ( nums[ pos] , visit ( nums, left, pos- 1 ) , visit ( nums, pos+ 1 , right) ) ; return root; } TreeNode* sortedArrayToBST ( vector< int > & nums) {
return visit ( nums, 0 , nums. size ( ) - 1 ) ; }
} ;
代码实现（四刷C++ DAY134 迭代）
class Solution {
public : vector< int > inorderTraversal ( TreeNode* root) {
struct TreeNode * pos = root; stack< TreeNode* > stack; vector< int > ret; while ( stack. size ( ) || pos) {
while ( pos) {
stack. emplace ( pos) ; pos = pos-> left; } if ( stack. size ( ) ) {
ret. emplace_back ( stack. top ( ) -> val) ; pos = stack. top ( ) -> right; stack. pop ( ) ; } } return ret; }
} ;
代码实现（五刷自解 DAY 225 C++）
class Solution {
public : vector< int > inorderTraversal ( TreeNode* root) {
vector< int > ret; stack< TreeNode* > stack; TreeNode* ptr = root; while ( ! stack. empty ( ) || ptr) {
while ( ptr) {
stack. emplace ( ptr) ; ptr = ptr-> left; } ptr = stack. top ( ) ; stack. pop ( ) ; ret. emplace_back ( ptr-> val) ; ptr = ptr-> right; } return ret; }
} ;
代码实现（六刷自解 DAY 274 C++）
class Solution {
public : vector< int > inorderTraversal ( TreeNode* root) {
stack< TreeNode* > stack; vector< int > ans; TreeNode* ptr = root; while ( ! stack. empty ( ) || ptr) {
while ( ptr) {
stack. emplace ( ptr) ; ptr = ptr-> left; } ptr = stack. top ( ) ; stack. pop ( ) ; ans. emplace_back ( ptr-> val) ; ptr = ptr-> right; } return ans; }
} ;
代码实现（七刷自解 DAY 4 Golang）
func inorderTraversal ( root * TreeNode) [ ] int {
stack, ptr, ret := [ ] * TreeNode{
} , root, [ ] int {
} for ptr != nil || len ( stack) != 0 {
for ptr != nil {
stack, ptr = append ( stack, ptr) , ptr. Left} ptr = stack[ len ( stack) - 1 ] stack = stack[ : len ( stack) - 1 ] ret, ptr = append ( ret, ptr. Val) , ptr. Right} return ret
}
