Linked List就是特殊化的Tree
Tree就是特殊化的Graph
二叉搜索树
98.验证二叉搜索树
思路:法一:做一次中序遍历In-order,保留前继节点即可 O(n)
法二:Recursion:递归函数(参数 min ,max)
max <-- 递归函数(node.left)
min <-- 递归函数(node.right)
max <root ; min>root 都成立即为BST O(n)
235.二叉树的最近公共祖先
思路:法一:Path:找路径 ,需有父亲指针,行不通
法二:从上往下找路径 ,Path1和Path2并记录下来 O(n)
法三:Recursion 引入辅助函数 -findPorQ(root,p,q)
分别对左子树和右子树引入辅助函数 O(n)
236.二叉搜索树的最近公共祖先