Flatten a binary tree to a fake "linked list" in pre-order traversal.
Here we use the right pointer in TreeNode as the next pointer in ListNode.
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
分析：
把所有的树节点按照PRE-ORDER的顺序存在ArrayList里面，然后遍历ArrayList里的节点，调整它们的left and right child指针。
/**
* 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
* cnblogs.com/beiyeqingteng
*/
public void flatten(TreeNode root) {
// write your code here
ArrayList<TreeNode> list = new ArrayList<TreeNode>();
preOrder(root, list); for (int i = ; i < list.size(); i++) {
list.get(i).left = null;
if (i == list.size() - ) {
list.get(i).right = null;
} else {
list.get(i).right = list.get(i + );
}
}
} public void preOrder(TreeNode root, ArrayList<TreeNode> list) {
if (root != null) {
list.add(root);
preOrder(root.left, list);
preOrder(root.right, list);
}
}
}
自己后来写出的方法：
public class Solution {
public void flatten(TreeNode root) {
helper(root);
}
public TreeNode helper(TreeNode root) {
if (root == null) return root;
TreeNode leftHead = helper(root.left);
TreeNode rightHead = helper(root.right);
root.left = null;
if (leftHead != null) {
root.right = leftHead;
TreeNode current = root;
while (current.right != null) {
current = current.right;
}
current.right = rightHead;
}
return root;
}
}
还有一种是递归的方式，下面的方法参考了另一个网友的做法，觉得这种方法非常容易理解，而且具有一般性。
解法2：递归构建
假设某节点的左右子树T(root->left)和T(root->right)已经flatten成linked list了：
1
/ \
2 5
\ \
3 6 <- rightTail
\
4 <- leftTail
如何将root、T(root->left)、T(root->right) flatten成一整个linked list？显而易见：
temp = root->right
root->right = root->left
root->left = NULL
leftTail->right = temp
这里需要用到已经flatten的linked list的尾部元素leftTail, rightTail。所以递归返回值应该是生成的整个linked list的尾部。
class Solution {
public void flatten(TreeNode root) {
flattenBT(root);
}
TreeNode flattenBT(TreeNode root) {
if(root == null) return null;
TreeNode leftTail = flattenBT(root.left);
TreeNode rightTail = flattenBT(root.right);
10 if(root.left != null) {
TreeNode temp = root.right;
root.right = root.left;
root.left = null;
leftTail.right = temp;
}
17 if(rightTail != null) return rightTail;
18 if(leftTail != null) return leftTail;
19 return root;
}
}
需注意几个细节
ln 10：只有当左子树存在时才将它插入右子树中
ln 17-19：返回尾部元素时，需要特殊处理 (1) 有右子树的情况，(2) 无右子树但有左子树的情况，(3)左右子树均不存在的情况。
Reference:
http://bangbingsyb.blogspot.com/2014/11/leetcode-flatten-binary-tree-to-linked.html