LeetCode hot100——二叉树展开为链表

题目给你二叉树的根结点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]提示树中结点数在范围[0, 2000]内-100 Node.val 100进阶你可以使用原地算法O(1)额外空间展开这棵树吗题解/** * 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) { TreeNode cur root; while(cur ! null){ //当前节点存在左子树 if(cur.left ! null){ //找左子树最右节点 TreeNode pre cur.left; while(pre.right ! null){ pre pre.right; } //当前右子树接到左子树最右子树 pre.right cur.right; //左子树挪到右子树左子树置空 cur.right cur.left; cur.left null; } cur cur.right; } } }思路当前节点cur不为空如果 cur 有左子树找到左子树的最右节点把最右节点的right接 cur 的右孩子cur 的右指针指向 cur.leftcur.left nullcur cur.right继续循环