【java】leetcode 二叉树展开为链表

leetcode114 .二叉树展开为链表

114 leetcode 链接。可以打开测试

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

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

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [0]
输出：[0]

解题思路

题目中，说展开后和先序遍历的顺序相同。那我们就可以先去先序遍历这个二叉树，按先序遍历把节点放进集合中，然后重构出一个单链表。

代码演示:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public void flatten(TreeNode root) {ArrayList<TreeNode> list= new ArrayList();process(root,list);for(int i = 0; i < list.size() - 1;i++){//只有右子树，来构造单链表list.get(i).right = list.get(i+1);//左子树置为空list.get(i).left = null;}}/*** 先序遍历 把节点加入到集合中*/public  void process(TreeNode root, ArrayList<TreeNode> list){if(root == null){return ;}list.add(root);process(root.left,list);process(root.right,list);}
}

二叉树专题：

填充每个节点的下一个右侧节点指针(java)

LeetCode: 二叉树的直径(java)

从前序与中序遍历序列构造二叉树（java）

leetcode二叉树中的最大路径和(java)

计算二叉树中最大的二叉搜索子树的大小(节点数量)

给定一棵二叉树的头节点,返回这颗二叉树中最大的二叉搜索子树的头节点

二叉树专题-求两个节点的最低公共祖先