114. 二叉树展开为链表 | LeetCode算法题解

题目描述

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

将其展开为：

思路

大体思路就是左子树移到右子树的位置，右子树接在之后。每一棵子树也要同样展开，就是递归。

解法

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
  if (!root || (!root.left && !root.right)) return root;

  const right = root.right;
  root.right = flatten(root.left);
  root.left = null;

  let tail = root;
  while (tail.right) {
    tail = tail.right;
  }

  tail.right = flatten(right);
  return root;
};