二叉树展开为链表(力扣热题HOT100 之 力扣114)Java

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

一、题目描述



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

展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。


展开后的单链表应该与二叉树 先序遍历 顺序相同。

 

示例 1:

a36ce447a0de4da3a82acafc8ef37bc6.png



输入: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) 额外空间)展开这棵树吗?


二、思路讲解


     

题目要求按先序遍历的顺序,那么很自然地想到递归方式先序遍历每个节点,并保存到列表中,然后再串连起来。


三、Java代码实现



/**
 * 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 {
    List<TreeNode> list = new ArrayList<>();
    public void flatten(TreeNode root) {
        dfs(root);
        TreeNode head = new TreeNode(0);
        TreeNode p = head;
        for(TreeNode node : list){
            p.right = node;
            p.left = null;
            p = p.right;
        }
        System.out.println(head.right);
    }
    void dfs(TreeNode node){
        if(node==null){
            return;
        }
        list.add(node);
        dfs(node.left);
        dfs(node.right);
    }
}



四、时空复杂度分析


     

时间复杂度:        O(N)

     

空间复杂度:        O(N)


五、进阶



原地改变树的结构。我们可以将第一个左节点不为空的节点(图中的节点1)的右节点(节点2)移到节点2的最后一个右子节点(节点4)之后,然后再将当前节点左子节点(节点2)移到右子节点位置上。就这样重复操作每一个右子节点不为空的节点。

7f1bf8ea663742ac9a26313da73f58ac.png


/**
 * 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 p = root;
        while(p!=null){
            if(p.left!=null){
                TreeNode next = p.left;
                TreeNode pre = p.left;
                while(pre.right!=null){
                    pre = pre.right;
                }
                pre.right = p.right;
                p.right = next;
                p.left = null;
            }
            p = p.right;
        }
    }
}


时间复杂度:        O(N)

     

空间复杂度:        O(1)


相关文章
|
1天前
|
存储 算法 Java
Java数据结构与算法:线性数据结构之链表
Java数据结构与算法:线性数据结构之链表
|
4天前
|
算法 Java
[Java·算法·简单] LeetCode 283. 移动零
[Java·算法·简单] LeetCode 283. 移动零
12 2
|
4天前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
12 2
|
7天前
|
算法
二刷力扣--二叉树(3)
二刷力扣--二叉树(3)
|
7天前
二刷力扣--二叉树(2)
二刷力扣--二叉树(2)
|
7天前
二刷力扣--二叉树(1)基础、遍历
二刷力扣--二叉树(1)基础、遍历
|
7天前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
11天前
|
存储 算法 数据可视化
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
|
11天前
|
存储 算法 数据可视化
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
|
11天前
|
算法 数据可视化 数据挖掘
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )