Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3}
,
1 \ 2 / 3
return [3,2,1]
.
Note: Recursive solution is trivial, could you do it iteratively?
Subscribe to see which companies asked this question
解答
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Return an array of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */ int* postorderTraversal(struct TreeNode* root, int* returnSize) { ], top = -, i = ; ); struct TreeNode *visit = NULL; != top||NULL != root){ while(NULL != root){ stack[++top] = root; root = root->left; } root = stack[top]; if(NULL == root->right||visit == root->right){ return_array[i++] = root->val; top--; visit = root; root = NULL; } else{ root = root->right; } } *returnSize = i; return return_array; }