用了基于stack的中序遍历，记录一下last，就很简单了。
|
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
|
#include <stack>/*树结点的定义(请不要在代码中定义该结构)struct TreeNode { TreeNode *left, *right;
bool isLeftThread, isRightThread;
}*/void
convertToThreadedTree(TreeNode *root) {
stack<TreeNode*> stak;
TreeNode *n = root;
TreeNode *last = NULL;
while
(n != NULL || !stak.empty()) {
if
(n != NULL) {
stak.push(n);
n = n->left;
} else
{
n = stak.top();
stak.pop();
// visit n
if
(last != NULL) {
if
(last->right == NULL) {
last->right = n;
last->isRightThread = true;
}
if
(n->left == NULL) {
n->left = last;
n->isLeftThread = true;
}
}
last = n;
n = n->right;
}
}
} |