Flatten a binary tree to a fake "linked list" in pre-order traversal.
Here we use the right pointer in TreeNode as the next pointer in ListNode.
Notice
Don't forget to mark the left child of each node to null. Or you will get Time Limit Exceeded or Memory Limit Exceeded.
1
\
1 2
/ \ \
2 5 => 3
/ \ \ \
3 4 6 4
\
5
\
6
LeetCode上的原题，请参见我之前的博客Flatten Binary Tree to Linked List。
解法一：
class Solution { public: /** * @param root: a TreeNode, the root of the binary tree * @return: nothing */ void flatten(TreeNode *root) { if (!root) return; stack<TreeNode*> s; s.push(root); while (!s.empty()) { TreeNode *t = s.top(); s.pop(); if (t->left) { TreeNode *r = t->left; while (r->right) r = r->right; r->right = t->right; t->right = t->left; t->left = NULL; } if (t->right) s.push(t->right); } } };
解法二：
class Solution { public: /** * @param root: a TreeNode, the root of the binary tree * @return: nothing */ void flatten(TreeNode *root) { if (!root) return; if (root->left) flatten(root->left); if (root->right) flatten(root->right); TreeNode *t = root->right; root->right = root->left; root->left = NULL; while (root->right) root = root->right; root->right = t; } };
解法三：
class Solution { public: /** * @param root: a TreeNode, the root of the binary tree * @return: nothing */ void flatten(TreeNode *root) { TreeNode *cur = root; while (cur) { if (cur->left) { TreeNode * t = cur->left; while (t->right) t = t->right; t->right = cur->right; cur->right = cur->left; cur->left = NULL; } cur = cur->right; } } };
本文转自博客园Grandyang的博客，原文链接：将二叉树展开成链表[LintCode] Flatten Binary Tree to Linked List ，如需转载请自行联系原博主。