LeetCode | 使用 “自带栈” 解决中序遍历

Problem

94. 二叉树的中序遍历

思路

我们都知道中序遍历是左边——>中间——>右边

解题方法

1. 一直向左边走
2. 到达左边尽头后弹出并打印，然后向右边走一个。
3. 继续一直向左边走。
4. 到达左边尽头后弹出并打印，然后向右边走一个。
5. 结束条件是p和栈S都为空。

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

typedef struct stackNode {
	struct TreeNode *data;
	struct stackNode *next;
} stackNode;
typedef stackNode* Stack;

void Push(Stack* S, struct TreeNode *BTNode) {
	if (*S) {
		stackNode *p = (stackNode*)malloc(sizeof(stackNode));
		p->data = BTNode;
		p->next = *S;
		*S = p;
	} else {
		stackNode *p = (stackNode*)malloc(sizeof(stackNode));
		p->data = BTNode;
		p->next = NULL;
		*S = p;
	}
}

struct TreeNode *Pop(Stack *S) {
	struct TreeNode *p = (*S)->data;
	stackNode *sp = *S;
	(*S) = (*S)->next;
	free(sp);
	return p;
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    Stack S = NULL;
	struct TreeNode *p = root;
    int *a = (int*)malloc(sizeof(int)*100), *q = a;
	while(p || S) {
		if(p) {
			Push(&S, p);
			p = p->left;
		} else {
			p = Pop(&S);
			*(q++) = p->val;
			p = p->right;
		}
	}
    *returnSize = q - a;
    return a;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56