• Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place. For example,
Given 1. 1 2. / \ 3. 2 5 4. / \ \ 5. 3 4 6

The flattened tree should look like: 1. 1 2. \ 3. 2 4. \ 5. 3 6. \ 7. 4 8. \ 9. 5 10. \ 11. 6

给定一颗二叉树，将其扁平化处理，我们可以看到处理之后的节点顺序其实跟前序遍历原二叉树的一致，所以我们只需要前序遍历二叉树同时处理就可以了。代码如下： 1. class Solution { 2. public: 3. void flatten(TreeNode root) { 4. if(!root) { 5. return; 6. } 7. 8. vector ns; 9. TreeNode dummy(0); 10. 11. TreeNode n = &dummy; 12. 13. ns.push_back(root); 14. 15. while(!ns.empty()) { 16. TreeNode* p = ns.back(); 17. ns.pop_back(); 18. 19. //挂载到右子树 20. n->right = p; 21. n = p; 22. 23. 24. //右子树压栈 25. if(p->right) { 26. ns.push_back(p->right); 27. p->right = NULL; 28. } 29. 30. //左子树压栈 31. if(p->left) { 32. ns.push_back(p->left); 33. p->left = NULL; 34. } 35. } 36. } 37. };