Open Linjiayu6 opened 4 years ago
class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
_len = len(postorder)
if _len == 0 or _len == 1 or _len == 2: return True
root_val = postorder.pop(-1)
i = 0
while i < len(postorder):
if postorder[i] > root_val: break
i += 1
left = postorder[0: i]
right = postorder[i: ]
# 判断right所有值是否均大于 root_val
for r in right:
if r < root_val: return False
r = self.verifyPostorder(left)
l = self.verifyPostorder(right)
if r == False or l == False: return False
return True
都是 深度优先遍历, 可以去看看树🌲的前中后序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
# 中序遍历 left, root, right
if root is None: return None
stack = [(root, 'light')]
i = 1
while stack:
(node, flag) = stack.pop()
if node:
if flag == 'light':
if node.right: stack.append((node.right, 'light'))
stack.append((node, 'grey'))
if node.left: stack.append((node.left, 'light'))
else:
if i == k: return node.val
else: i+= 1
"""
# Definition for a Node.
class Node(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
"""
class Solution(object):
def treeToDoublyList(self, root):
"""
:type root: Node
:rtype: Node
"""
if root is None: return None
# 中序遍历 左 中 右
stack = [(root, 'light')]
head = Node(None) # 指针
prevtmp = head
while stack:
(node, key) = stack.pop()
if node:
if key == 'light':
if node.right: stack.append((node.right, 'light'))
stack.append((node, 'grey'))
if node.left: stack.append((node.left, 'light'))
else:
prevtmp.right = node # 指向后面的节点
node.left = prevtmp
prevtmp = node
_minNode = head.right
_minNode.left = prevtmp
prevtmp.right = _minNode
return head.right
0 - 概念
左边子树值 < root.val 右边子树值 > root.val
通过使用【中序遍历】 left => root => right 路径判断 是否是递增的序列