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