前面几篇文章分享了如何非递归的前中后序遍历，其实掌握前中后序遍历已经可以解决90%的题了，当然你肯定想学的更多。
先看leetcode的一个场景。
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
看完题目，是不是想着先前序遍历一遍，将所有节点存下来，然后改变一下节点的指针指向，相信大部分人的思路也是这样（代码后面给出），先说另一个思路，它不是要前序遍历的顺序构造一个链表树么，那我们反前序遍历，将根节点存储下来，依次递归回溯，就得到了题目的答案。
代码非常的简洁，不过需要深刻理解这个递归过程。
class Solution { public: TreeNode* preNode; // 用于记录上一个处理过的节点的指针 void flatten(TreeNode* root) { if (root == NULL) return; // 终止条件：当节点为空时，直接返回 flatten(root->right); // 先对右子树进行递归调用，保证右子树已经被拉平 flatten(root->left); // 再对左子树进行递归调用，保证左子树已经被拉平 root->left = NULL; // 将当前节点的左子树置为空 root->right = preNode; // 将当前节点的右子树指向上一个处理过的节点 preNode = root; // 更新preNode为当前节点，以备下一次递归处理 // 递归调用到这里时，当前节点已经处理完毕，它的左子树和右子树都已经被拉平并且连接好了 } };
之前思路的代码：
class Solution { public: vector<int> res; // 用于存储中序遍历结果的容器 void inorder(TreeNode *root) { stack<TreeNode *> s; s.push(root); while (root != nullptr || s.size() > 0) { while (root != nullptr) { TreeNode *cur = s.top(); s.pop(); res.push_back(cur->val); // 将当前节点的值保存到结果容器中 if (cur->right != nullptr) s.push(cur->right); // 将右子节点入栈 if (cur->left != nullptr) s.push(cur->left); // 将左子节点入栈 } } } void flatten(TreeNode* root) { inorder(root); // 对二叉树进行中序遍历，得到展开后的顺序 TreeNode *r = new TreeNode(-1); TreeNode *next = r; for (int i = 0; i < res.size(); i++) { TreeNode *temp = new TreeNode(res[i]); // 依次创建节点 next->right = temp; // 将节点接到结果链表的后面 next = temp; } root = r->right; // 更新根节点为展开后的链表 } };
leetcode官方比较有意思的题解
寻找前驱节点
注意到前序遍历访问各节点的顺序是根节点、左子树、右子树。如果一个节点的左子节点为空，则该节点不需要进行展开操作。如果一个节点的左子节点不为空，则该节点的左子树中的最后一个节点被访问之后，该节点的右子节点被访问。该节点的左子树中最后一个被访问的节点是左子树中的最右边的节点，也是该节点的前驱节点。因此，问题转化成寻找当前节点的前驱节点。
具体做法是，对于当前节点，如果其左子节点不为空，则在其左子树中找到最右边的节点，作为前驱节点，将当前节点的右子节点赋给前驱节点的右子节点，然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点设为空。对当前节点处理结束后，继续处理链表中的下一个节点，直到所有节点都处理结束
class Solution { public: void flatten(TreeNode* root) { TreeNode *curr = root; // 当前节点指针，用于遍历二叉树的每个节点 while (curr != nullptr) { if (curr->left != nullptr) { // 如果当前节点的左子节点存在 auto next = curr->left; // 将当前节点的左子节点保存为next auto predecessor = next; // 用predecessor指针指向next，用于找到next的前驱节点 while (predecessor->right != nullptr) { predecessor = predecessor->right; // 找到next的右子树的最右边节点，即next的前驱节点 } predecessor->right = curr->right; // 将next的前驱节点的右子节点指向当前节点的右子树 curr->left = nullptr; // 将当前节点的左子节点置为空 curr->right = next; // 将当前节点的右子节点设置为next } curr = curr->right; // 移动当前节点指针，继续遍历下一个节点 } } };
