1 // 1、如果当前节点没有左儿子,则打印当前节点的值,然后进入右子树; 2 // 2、如果当前节点有左儿子,则找当前节点的前驱。 3 // (1) 如果前驱节点的右儿子为空,说明左子树没遍历过,则进入左子树遍历,并将前驱节点的右儿子置成当前节点,方便回溯; 4 // (2) 如果前驱节点的右儿子为当前节点,说明左子树已被遍历过,则将前驱节点的右儿子恢复为空,然后打印当前节点的值,然后进入右子树继续遍历; 5 class Solution 6 { 7 public: 8 void recoverTree(TreeNode* root) 9 { 10 while (root) 11 { 12 if (!root->left) 13 { 14 cout << root->val << endl; 15 root = root->right; 16 } 17 else 18 { 19 auto p = root->left; 20 while (p->right && p->right != root) p = p->right; 21 22 if (!p->right) p->right = root, root = root->left; 23 else 24 { 25 p->right = NULL; 26 cout << root->val << endl; 27 root = root->right; 28 } 29 } 30 } 31 } 32 };
原文:https://www.cnblogs.com/yuhong1103/p/13287110.html