Code Ganker: Flatten Binary Tree to Linked List -- LeetCode

2014年4月14日星期一

Flatten Binary Tree to Linked List -- LeetCode

原题链接: http://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/
这是树的题目，要求把一颗二叉树按照先序遍历顺序展成一个链表，不过这个链表还是用树的结果，就是一直往右走（没有左孩子）来模拟链表。老套路还是用递归来解决，维护先序遍历的前一个结点pre，然后每次把pre的左结点置空，右结点设为当前结点。这里需要注意的一个问题就是我们要先把右子结点保存一下，以便等会可以进行递归，否则有可能当前结点的右结点会被覆盖，后面就取不到了。算法的复杂度时间上还是一次遍历，O(n)。空间上是栈的大小，O(logn)。代码如下：

public void flatten(TreeNode root) {
    ArrayList<TreeNode> pre = new ArrayList<TreeNode>();
    pre.add(null);
    helper(root, pre);
}
private void helper(TreeNode root, ArrayList<TreeNode> pre)
{
    if(root == null)
        return;
    TreeNode right = root.right;
    if(pre.get(0)!=null)
    {
        pre.get(0).left = null;
        pre.get(0).right = root;
    }
    pre.set(0,root);
    helper(root.left, pre);
    helper(right, pre);
}

树的题目讨论得比较多了，主要思路就是递归，考虑好递归条件和结束条件，有时候如果递归过程会对树结构进行修改的话，要先保存一下结点。

4 条评论:

Patrick2014年10月12日 22:12
我有两个解法，都不需要保存右子结点，一个是递归的，一个是循环的；递归的我return出插入的地方的节点就可以不用保存右子结点，循环的，我每次在遇到有左孩子，我就找出插入节点，然后直到走到最后。但我感觉我的循环的还可以进一步提高，因为其实在查找查找节点的时候也可以做flatten. 循环的时间复杂度应该是 O（n^2）所以我感觉应该还有进步空间，但因为过了，我就没仔细琢磨，你要是有空就帮我看看阿。
循环：
public class Solution {
public void flatten(TreeNode root) {
if(root==null) return;
while(root.left!=null || root.right!=null){
if (root.left!=null){
TreeNode temp=helper(root.left);
temp.right=root.right;
root.right=root.left;
root.left=null;
}
root=root.right;
}
}
public TreeNode helper(TreeNode root){
TreeNode cur=root;
while(cur.left!=null || cur.right!=null){
cur=(cur.right==null)? cur.left : cur.right;
}
return cur;
}
}
递归：
public class Solution {
public void flatten(TreeNode root) {
if(root==null) return;
helper(root);
}
public TreeNode helper(TreeNode node){
if(node==null) return null;
if(node.left==null && node.right==null){
return node;
}
if(node.left!=null && node.right!=null){
TreeNode temp=helper(node.left);
temp.right=node.right;
node.right=node.left;
node.left=null;
return helper(temp.right);
}
if(node.left!=null && node.right==null){
TreeNode temp=helper(node.left);
node.right=node.left;
node.left=null;
return temp;
}
return helper(node.right);
}
}
回复删除
回复
Patrick2014年10月12日 22:13
怎么能把代码复制过来还能保持格式阿？？
回复删除
回复

添加评论