有关二叉树的做题笔记，Python实现
二叉树的定义
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
235. 二叉搜索树的最近公共祖先 Lowest Common Ancestor of a Binary Search Tree
第一种方法：用236题.二叉树的最近公共祖先的方法
第二种方法：利用二叉搜索树的左子树都小于父亲节点，右子树都大于父亲节点的特性，可以把第一种方法简化一下
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
return root
第三种方法：跟方法二的思路一样，把递归改成循环
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
