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

  1. // Flatten Binary Tree to Linked List
  2. // 递归版1，时间复杂度O(n)，空间复杂度O(logn)
  3. class Solution {
  4. public:
  5.     void flatten(TreeNode *root) {
  6.         if (root == nullptr) return;  // 终止条件
  8.         flatten(root->left);
  9.         flatten(root->right);
  11.         if (nullptr == root->left) return;
  13.         // 三方合并，将左子树所形成的链表插入到root和root->right之间
  14.         TreeNode *p = root->left;
  15.         while(p->right) p = p->right; //寻找左链表最后一个节点
  16.         p->right = root->right;
  17.         root->right = root->left;
  18.         root->left = nullptr;
  19.     }
  20. };

递归版2

  1. // Flatten Binary Tree to Linked List
  2. // 递归版2
  3. // @author 王顺达(http://weibo.com/u/1234984145)
  4. // 时间复杂度O(n)，空间复杂度O(logn)
  5. class Solution {
  6. public:
  7.     void flatten(TreeNode *root) {
  8.         flatten(root, NULL);
  9.     }
  10. private:
  11.     // 把root所代表树变成链表后，tail跟在该链表后面
  12.     TreeNode *flatten(TreeNode *root, TreeNode *tail) {
  13.         if (NULL == root) return tail;
  15.         root->right = flatten(root->left, flatten(root->right, tail));
  16.         root->left = NULL;
  17.         return root;
  18.     }
  19. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/binary-tree/traversal/flatten-binary-tree-to-linked-list.html