Here we use the right pointer in TreeNode as the next pointer in ListNode.
Don‘t forget to mark the left child of each node to null. Or you will get Time Limit Exceeded or Memory Limit Exceeded.
Example 1:
Input:{1,2,5,3,4,#,6}
Output：{1,#,2,#,3,#,4,#,5,#,6}
Explanation：
1
/ 2 5
/ \ 3 4 6
1
2
3
4
5
6
Example 2:
Input:{1}
Output:{1}
Explanation：
1
1
Do it in-place without any extra memory.
思路：使用 Divide & Conquer 分治函数 return 这个 tree 的最后一个点
public class Solution {
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
public void flatten(TreeNode root) {
helper(root);
}
// flatten root and return the last node
private TreeNode helper(TreeNode root) {
if (root == null) {
return null;
}
TreeNode leftLast = helper(root.left);
TreeNode rightLast = helper(root.right);
// connect leftLast to root.right
if (leftLast != null) {
leftLast.right = root.right;
root.right = root.left;
root.left = null;
}
if (rightLast != null) {
return rightLast;
}
if (leftLast != null) {
return leftLast;
}
return root;
}
}
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
private TreeNode lastNode = null;
public void flatten(TreeNode root) {
if (root == null) {
return;
}
if (lastNode != null) {
lastNode.left = null;
lastNode.right = root;
}
lastNode = root;
TreeNode right = root.right;
flatten(root.left);
flatten(right);
}
}
Flatten Binary Tree to Linked List
原文：https://www.cnblogs.com/FLAGyuri/p/12078460.html