题目

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

  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

题意

将一个二叉树的结构变为只有右子树的一直链，且顺序为原二叉树的前序遍历。

思路

方法有点像 Morris Traversal：如果当前结点root存在左子树，则将该结点的右子树接在其左子树最右结点的右边，再将root的左子树变为右子树，令 root = root.right 重复上述操作。
image.png

代码实现

Java

  1. class Solution {
  2.     public void flatten(TreeNode root) {
  3.         while (root != null) {
  4.             if (root.left != null) {
  5.                 TreeNode x = root.left;
  6.                 while (x.right != null) {
  7.                     x = x.right;
  8.                 }
  9.                 x.right = root.right;
  10.                 root.right = root.left;
  11.                 root.left = null;
  12.             }
  13.             root = root.right;
  14.         }
  15.     }
  16. }

JavaScript

  1. /**
  2.  * @param {TreeNode} root
  3.  * @return {void} Do not return anything, modify root in-place instead.
  4.  */
  5. var flatten = function (root) {
  6.   while (root) {
  7.     if (root.left) {
  8.       let tmp = root.left
  9.       while (tmp.right) tmp = tmp.right
  10.       tmp.right = root.right
  11.       root.right = root.left
  12.       root.left = null
  13.     }
  14.     root = root.right
  15.   }
  16. }