leetcode [114]Flatten Binary Tree to Linked List

佚名 6年前 (2019-04-14) 随笔 1655人围观抢沙发百度已收录

题目大意：

将一个二叉树变为一个链表

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

解法：

这道题目输出结果就是采用前序遍历二叉树的结果，将这个结果变为一个双向链表。但是题目的要求是在原数据结构上进行改变，而不是采用前序遍历的结果新建一个链表。这道题目剑指offer上面也有，做过很多次，但是记不得，最讨厌做树相关的题目了。

参考了一下网上的解法，看起来还是很容易理解的，就是将左右子树递归的变成链表，再和当前节点相连接。但是感觉自己很难想出来。

解法主要是下面三步：

1.将左子树转换成链表

2.将右子树转换成链表

3.将当前节点的左指针指向空，右节点指向leftList.head，然后将leftList.end指向rightList.head。

java:

class Solution {
    public void flatten(TreeNode root) {
        if(root==null) return;
        TreeNode left=root.left;
        TreeNode right=root.right;
        
        flatten(left);
        flatten(right);
        
        root.left=null;
        root.right=left;
        TreeNode cur=root;
        while(cur.right!=null) cur=cur.right;
        cur.right=right;
    }
}