leetcode-897 递增顺序搜索树 DFS+栈实现

leetcode-897 递增顺序搜索树 DFS+栈实现

1. 题目

给你一棵二叉搜索树,请你 按中序遍历 将其重新排列为一棵递增顺序搜索树,使树中最左边的节点成为树的根节点,并且每个节点没有左子节点,只有一个右子节点。

2. 思路

  • 使用递归实现二叉树的中序遍历较为简单,先遍历左子树,在输出当前节点的值,再遍历右子树即可
def bst(root):
    if root:
        bst(root.left)
        print(root.value)
        bst(root.right)
  • 使用栈(数组)来实现对二叉树的遍历,遇到节点有非空左子树时,将其存入栈中,此循环结束时,访问该节点,再访问该节点的右节点

3. Code

  • 递归实现
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def __init__(self):
        self.res=None
        self.cur=None
    def increasingBST(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        else:
            self.res=TreeNode()
            self.cur=self.res
            self.dsf(root)
            return self.res.right
    def dsf(self,root):
        if root.left:
            self.dsf(root.left)
        self.cur.right=TreeNode(root.val)
        print(root.val)
        self.cur=self.cur.right
        if root.right:
            self.dsf(root.right)
  • 栈实现
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        else:
            #首节点被初始化为0,返回时返回res.right
            res=TreeNode()
            #使用cur暂存当前节点
            cur=res
            stack=[]
            while root or stack:
                while root:
                    stack.append(root)
                    root=root.left
                node=stack.pop()
                cur.right=TreeNode(node.val)
                cur=cur.right
                root=node.right
            return res.right
上一篇:powercli The SSL connection could not be established, see inner exception. 问题解决


下一篇:小白的Python之路 day4 生成器并行运算