Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree[1,null,2,3],
1
\
2
/
3
return
[1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
中序遍历
中序遍历是首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。在遍历上图[1,2,3]组成的二叉树时，遍历结果为[1,3,2]
方法
中序遍历二叉树，如果不用递归的方式，同样需要借助栈。
将当前节点压栈，然后将当前节点指向左子节点压栈，循环直至左节点为空。然后从栈里取出节点，同时取出节点值。然后将当前节点指向右子节点，若当前节点不为空，循环开始的过程。直至当前节点为空并且栈为空的时候，退出循环。
c代码
#include <assert.h>
#include <stdlib.h>
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* inorderTraversal(struct TreeNode* root, int* returnSize) {
struct TreeNode* node;
struct TreeNode** nodes = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * 1000);
node = root;
int nodesTop = 0;
int* vals = (int *)malloc(sizeof(int) * 1000);
int valsTop = 0;
while(node!=NULL || nodesTop!=0) {
while(node != NULL) {
nodes[nodesTop++] = node;
node = node->left;
}
node = nodes[--nodesTop];
vals[valsTop++] = node->val;
node = node->right;
}
*returnSize = valsTop;
return vals;
}
int main() {
struct TreeNode* root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
root->val = 1;
struct TreeNode* node1_2 = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node1_2->val = 2;
root->left = NULL;
root->right = node1_2;
struct TreeNode* node2_3 = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node2_3->val = 3;
node1_2->left = node2_3;
node1_2->right = NULL;
node2_3->left = NULL;
node2_3->right = NULL;
int returnSize = 0;
int* vals = inorderTraversal(root, &returnSize);
assert(returnSize == 3);
assert(vals[0] == 1);
assert(vals[1] == 3);
assert(vals[2] == 2);
return 0;
}
