LeetCode力扣第114题:多种算法实现 将二叉树展开为链表

简介: LeetCode力扣第114题:多种算法实现 将二叉树展开为链表

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

python源码解读

程序员必备的数学知识与应用

题目描述

给定一个二叉树,原地将它展开为一个单链表。例如,给定二叉树:

1
   / \
  2   5
 / \   \
3   4   6

展开后应该变为:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

方法一:递归展开

解题步骤

  1. 如果树为空,直接返回。
  2. 递归展开左子树和右子树。
  3. 将左子树插入到右子树的位置。
  4. 将原来的右子树接到当前右子树的末端。
  5. 考虑到展开后没有左子节点,将左子节点设置为None

代码示例

class Solution:
    def flatten(self, root):
        if not root:
            return
        self.flatten(root.left)
        self.flatten(root.right)
        # 左右子树已经被拉平成一条链表
        left = root.left
        right = root.right
        # 将左子树作为右子树
        root.left = None
        root.right = left
        # 找到当前右子树(原左子树)的末端并连接原右子树
        p = root
        while p.right:
            p = p.right
        p.right = right

方法一的改进主要可以从两个方面进行:优化递归效率和空间使用。虽然基本递归方法简单直观,但它可能导致不必要的栈空间消耗,尤其是在处理非常深的树时可能会导致栈溢出。以下是几种改进策略:

改进1: 尾递归优化

虽然Python默认不支持尾递归优化,但我们可以尽可能减少递归中不必要的操作,将必要的操作移至递归调用之前执行,减少递归调用栈的深度。

改进代码示例

class Solution:
    def flatten(self, root):
        def flattenTree(node):
            if not node:
                return None
            
            # 如果节点是叶子节点,直接返回
            if not node.left and not node.right:
                return node
            
            # 递归平展左子树
            leftTail = flattenTree(node.left)
            rightTail = flattenTree(node.right)
            
            # 将左子树插入到右子树的地方
            if leftTail:
                leftTail.right = node.right
                node.right = node.left
                node.left = None
            
            # 返回最后的尾部节点
            return rightTail if rightTail else leftTail
        
        flattenTree(root)
改进2: 减少递归深度

尽可能地在每个节点处理完毕后立即释放其左子树的引用,减少Python垃圾回收器的压力,并减少递归深度。

改进代码示例

class Solution:
    def flatten(self, root):
        # Helper function to perform flatten operation
        def flattenNode(node):
            if not node:
                return None
            # Flatten the left and right subtree
            left_last = flattenNode(node.left)
            right_last = flattenNode(node.right)
            # If there is a left subtree, weave it into the right subtree
            if left_last:
                left_last.right = node.right
                node.right = node.left
                node.left = None
            # The rightmost node is needed for linking to the parent node's right subtree
            return right_last if right_last else left_last
        flattenNode(root)

方法二:迭代展开

解题步骤

  1. 使用栈来辅助迭代过程。
  2. 每次取出栈顶元素,如果有右子节点先压栈,再压左子节点。
  3. 修改每个节点的右指针指向下一个栈顶元素,左指针设置为None

代码示例

class Solution:
    def flatten(self, root):
        if not root:
            return
        
        stack = [root]
        prev = None
        
        while stack:
            curr = stack.pop()
            if prev:
                prev.right = curr
                prev.left = None
            if curr.right:
                stack.append(curr.right)
            if curr.left:
                stack.append(curr.left)
            prev = curr

方法三:寻找前驱节点

解题步骤

  1. 对于每个节点,如果左子节点不为空,找到左子树的最右节点(前驱节点)。
  2. 将原右子树接到前驱节点的右边。
  3. 将左子树移到右边,左子树置为空。
  4. 继续处理链表中的下一个节点。

代码示例

class Solution:
    def flatten(self, root):
        curr = root
        while curr:
            if curr.left:
                pre = curr.left
                while pre.right:
                    pre = pre.right
                pre.right = curr.right
                curr.right = curr.left
                curr.left = None
            curr = curr.right

算法分析

  • 时间复杂度
  • 递归展开:(O(n)),每个节点访问一次。
  • 迭代展开:(O(n)),每个节点访问一次。
  • 寻找前驱节点:(O(n)),每个节点访问一次。
  • 空间复杂度
  • 递归展开:(O(n)),递归栈的空间。
  • 迭代展开:(O(n)),使用了额外的栈。
  • 寻找前驱节点:(O(1)),原地修改,不需要额外空间。

优劣势对比

  • 递归展开
  • 优点:实现简单直观。
  • 缺点:需要额外的栈空间来处理递归。
  • 迭代展开
  • 优点:避免了递归可能导致的栈溢出。
  • 缺点:需要使用栈来存储节点。
  • 寻找前驱节点
  • 优点:不需要额外空间,空间复杂度最优。
  • 缺点:代码逻辑相对复杂,需要处理更多的指针操作。

应用示例

这种技巧在处理需要将树结构线性化处理的场景非常有用,例如在图形界面开发中,需要按特定顺序访问或显示节点信息,或者在需要频繁查找、更新结点而又不频繁修改树结构的数据库和文件系统中。

欢迎关注微信公众号 数据分析螺丝钉


相关文章
|
13天前
|
算法 JavaScript
JS 【详解】二叉树(含二叉树的前、中、后序遍历技巧和算法实现)
JS 【详解】二叉树(含二叉树的前、中、后序遍历技巧和算法实现)
18 0
|
13天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
12 3
|
16天前
2670.找出不同元素数目差数组-力扣(LeetCode)
2670.找出不同元素数目差数组-力扣(LeetCode)
6 0
|
16天前
|
索引
821.字符的最短距离-力扣(LeetCode)
821.字符的最短距离-力扣(LeetCode)
9 0
|
17天前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
11 1
|
17天前
|
存储 Java
力扣经典150题第五十九题: 随机链表的复制
力扣经典150题第五十九题: 随机链表的复制
13 1
|
17天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
15 2
|
17天前
|
Java 索引
力扣经典150题第五十六题:环形链表
力扣经典150题第五十六题:环形链表
11 0
|
22天前
|
算法 Java
Java数据结构与算法:双向链表
Java数据结构与算法:双向链表
|
22天前
|
算法 Java
Java数据结构与算法:循环链表
Java数据结构与算法:循环链表