Python 检查二叉树是否为 BST 的程序
假设我们有一个二叉树;我们需要检查它是否为二叉搜索树。众所周知,BST 具有以下属性:
- 其所有左子树节点都小于当前节点值
- 其所有右子树节点都大于当前节点值
- 这些属性对所有节点递归成立
因此,如果输入类似于
则输出将为 True
为了解决这个问题,我们将遵循以下步骤:
- x := 树元素的中序遍历序列列表
- 如果 x 已排序,则
- 返回 true
- 返回 false
让我们看一下以下实现以更好地理解:
示例
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right class Solution: def solve(self, root): def inorder(root,l): if root is None: return inorder(root.left,l) l.append(root.data) inorder(root.right,l) l = [] inorder(root,l) return l == sorted(l) ob = Solution() root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8) print(ob.solve(root))
输入
root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8)
Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.
输出
True
广告