[LeetCode]114. Flatten Binary Tree to Linked List

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

将二叉树变成一条线每个节点只有一个右子节点，线的顺序为中序遍历

我的解：

函数返回已经flatten的数组，里面两个元素，是线的开头和结尾

public class Solution { public void flatten(TreeNode root) { if (root == null) { return; } dfs(root); } private TreeNode[] dfs(TreeNode root) { TreeNode[] res = {root, root}; TreeNode[] left; TreeNode[] right; TreeNode leftNode = root.left; TreeNode rightNode = root.right; root.left = null; if (leftNode != null) { left = dfs(leftNode); res[1].right = left[0]; res[1] = left[1]; } if (rightNode != null) { right = dfs(rightNode); res[1].right = right[0]; res[1] = right[1]; } return res; } }

Discuss最优解：

用参数pre记录当前要flatten的直线右下方所要连接的节点，flatten返回当前flatten后的直线左上角的头结点

public class Solution { public void flatten(TreeNode root) { flatten(root, null); } private TreeNode flatten(TreeNode root, TreeNode pre) { if (root == null) { return pre; } // 先右后左 pre = flatten(root.right, pre); pre = flatten(root.left, pre); root.right = pre; root.left = null; pre = root; return pre; } }