Leetcode 114. 二叉树展开为链表

傷城~ 2022-08-28 02:50 124阅读 0赞

## 题目 ##

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。  
展开后的单链表应该与二叉树 先序遍历 顺序相同。

### 示例 1： ###

输入：root = [1,2,5,3,4,null,6]
    输出：[1,null,2,null,3,null,4,null,5,null,6]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Ziz5YWJ5aSn55S35a2pIQ_size_20_color_FFFFFF_t_70_g_se_x_16]

### 示例 2： ###

输入：root = []
    输出：[]

### 示例 3： ###

输入：root = [0]
    输出：[0]

### 提示： ###

树中结点数在范围 [0, 2000] 内
    -100 <= Node.val <= 100

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## Java实现 ##

class Solution {
        
        private List<TreeNode> resultList  = new ArrayList<>();
        public void flatten(TreeNode root) {
        
            preOrder(root);
            for (int i = 0; i < resultList.size(); i++) {
        
                TreeNode t = resultList.get(i);
                t.left = null;
                if(i!=resultList.size()-1){
        
                    t.right = resultList.get(i+1);
                }else{
        
                    t.right = null;
                }
    
            }
        }
        // 先序遍历到结果数组
        void preOrder(TreeNode root){
        
            if(root!=null){
        
                resultList.add(root);
                preOrder(root.left);
                preOrder(root.right);
            }
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Ziz5YWJ5aSn55S35a2pIQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c21284db1c89458f8419b558bd1bb995.png