用了基于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; } }} |
原文：http://www.cnblogs.com/lautsie/p/3528890.html