leetcode [114]Flatten Binary Tree to Linked List

发布时间：2020-12-14 04:33:38 所属栏目：大数据来源：网络整理

导读：题目大意：将一个二叉树变为一个链表解法：这道题目输出结果就是采用前序遍历二叉树的结果，将这个结果变为一个双向链表。但是题目的要求是在原数据结构上进行改变，而不是采用前序遍历的结果新建一个链表。这道题目剑指offer上面也有，做过很多次，但是

题目大意：

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

解法：

这道题目输出结果就是采用前序遍历二叉树的结果，将这个结果变为一个双向链表。但是题目的要求是在原数据结构上进行改变，而不是采用前序遍历的结果新建一个链表。这道题目剑指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;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!