114.二叉树展开为链表

链接：114.二叉树展开为链表
难度：Medium
标签：栈、树、深度优先搜索、链表、二叉树
简介：给定一个二叉树，原地将它展开为链表。

题解 1 - typescript

• 编辑时间：2020-08-02
• 执行用时：120ms
• 内存消耗：40MB
• 编程语言：typescript
• 解法介绍：前序遍历。

function flatten(root: TreeNode | null): void {
  if (root === null || (root.left === null && root.right === null)) return;
  const list: TreeNode[] = [];
  _preorder(root);
  let node: TreeNode = root;
  for (let i = 1, l = list.length; i < l; i++) {
    const v = list[i];
    node.left = null;
    node.right = list[i];
    node = v;
    if (i === l - 1) {
      node.left = node.right = null;
    }
  }
  function _preorder(node: TreeNode | null): void {
    if (node === null) return;
    list.push(node);
    node.left !== null && _preorder(node.left);
    node.right !== null && _preorder(node.right);
  }
}

题解 2 - java

• 编辑时间：2020-02-21
• 执行用时：1ms
• 内存消耗：38.2MB
• 编程语言：java
• 解法介绍：使用前序遍历，再把遍历后的结果重新赋值到 right 上。

class Solution {
    LinkedList<TreeNode> list = new LinkedList<>();
	public void flatten(TreeNode root) {
		if (root == null||(root.left == null && root.right == null))
			return;
		preorder(root);
		TreeNode cur = root;
		for (int i = 0, len = list.size(); i < len; i++) {
			cur.right = list.remove(0);
			cur = cur.right;
		}
	}
	public void preorder(TreeNode node) {
		list.add(node);
		if (node.left != null)
			preorder(node.left);
		if (node.right != null)
			preorder(node.right);
		node.left = null;
		node.right = null;
	}
}