思路
一般树的问题可以借用递归模板进行处理,模板中主要是对当前root的处理:
def traverse(root){
#TODO 针对 当前root 做逻辑处理
traverse(root.left);
traverse(root.right);
}
以上模板也是一种“自顶向下”递归处理过程,及在调用的时候将优先遍历的位于“顶”层的元素传递到下层进行递归。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return recursion(root, null,null);
}
private boolean recursion(TreeNode root,Integer lower,Integer upper){
// ----------- 分割线 ------------
// 以下即为对当前 root 值的处理
if(root == null) return true;
int val = root.val;
if(lower != null && val <= lower) return false;
if(upper != null && val >= upper) return false;
// ------------ 分割线 --------------
if(!recursion(root.left,lower,val)) return false;
if(!recursion(root.right,val,upper)) return false;
return true;
}
}