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. public class Solution {
  4.     public void flatten(TreeNode root) {
  5.         if (root == null) return;  // 终止条件
  7.         flatten(root.left);
  8.         flatten(root.right);
  10.         if (root.left == null) return;
  12.         // 三方合并，将左子树所形成的链表插入到root和root->right之间
  13.         TreeNode p = root.left;
  14.         while(p.right != null) p = p.right; //寻找左链表最后一个节点
  15.         p.right = root.right;
  16.         root.right = root.left;
  17.         root.left = null;
  18.     }
  19. }

递归版2

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

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