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.         }
  8.         vector<TreeNode*> ns;
  9.         TreeNode dummy(0);
  11.         TreeNode* n = &dummy;
  13.         ns.push_back(root);
  15.         while(!ns.empty()) {
  16.             TreeNode* p = ns.back();
  17.             ns.pop_back();
  19.             //挂载到右子树
  20.             n->right = p;
  21.             n = p;
  24.             //右子树压栈
  25.             if(p->right) {
  26.                 ns.push_back(p->right);
  27.                 p->right = NULL;
  28.             }
  30.             //左子树压栈
  31.             if(p->left) {
  32.                 ns.push_back(p->left);
  33.                 p->left = NULL;
  34.             }
  35.         }
  36.     }
  37. };