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?
中序遍歷
中序遍歷是首先遍歷左子樹(shù)铣墨，然后訪問(wèn)根結(jié)點(diǎn)侈百，最后遍歷右子樹(shù)追他。在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)民逼，再訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。在遍歷上圖[1,2,3]組成的二叉樹(shù)時(shí)坟岔，遍歷結(jié)果為[1,3,2]
方法
中序遍歷二叉樹(shù)，如果不用遞歸的方式摔桦，同樣需要借助棧社付。
將當(dāng)前節(jié)點(diǎn)壓棧，然后將當(dāng)前節(jié)點(diǎn)指向左子節(jié)點(diǎn)壓棧邻耕，循環(huán)直至左節(jié)點(diǎn)為空鸥咖。然后從棧里取出節(jié)點(diǎn)，同時(shí)取出節(jié)點(diǎn)值兄世。然后將當(dāng)前節(jié)點(diǎn)指向右子節(jié)點(diǎn)啼辣，若當(dāng)前節(jié)點(diǎn)不為空，循環(huán)開(kāi)始的過(guò)程碘饼。直至當(dāng)前節(jié)點(diǎn)為空并且棧為空的時(shí)候熙兔，退出循環(huán)悲伶。
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;
}
擴(kuò)展
前序遍歷二叉樹(shù)
[LeetCode]144. Binary Tree Preorder Traversal
