程序员面试金典day9

Q1:请实现一个函数，检查一棵二叉树是否为二叉查找树。 给定树的根结点指针TreeNode* root，请返回一个bool，代表该树是否为二叉查找树。

思路

采用了递归，但实际上写成中序遍历是不是会更好一些

Code

python

# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None import sys class Checker: def subcheckBST(self,root,flag): if root==None: if flag==0: return (True,-sys.maxsize) return (True,sys.maxsize) tmp1=self.subcheckBST(root.left,0) if tmp1[0]==False or root.val<tmp1[1]: return (False,0) tmp2=self.subcheckBST(root.right,1) if tmp2[0]==False or root.val>tmp2[1]: return (False,0) if flag==0: return (True,tmp2[1] if tmp2[1]!=sys.maxsize else root.val) return (True,tmp1[1] if tmp1[1]!=-sys.maxsize else root.val) def checkBST(self, root): return self.subcheckBST(root,0)[0]

Q2:请设计一个算法，寻找二叉树中指定结点的下一个结点（即中序遍历的后继）。 给定树的根结点指针TreeNode* root和结点的值int p，请返回值为p的结点的后继结点的值。保证结点的值大于等于零小于等于100000且没有重复值，若不存在后继返回-1。

思路

写成中序遍历

Code

python

# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Successor: def bfs(self,root): if root==None: return self.bfs(root.left) self.Li.append(root.val) self.bfs(root.right) def findSucc(self, root, p): self.Li=[] self.bfs(root) ind=self.Li.index(p) if ind==-1 or ind==len(self.Li)-1: return -1 return self.Li[ind+1]