文章
问答
冒泡
LeetCode 每日一题

image.png

思路

一般树的问题可以借用递归模板进行处理,模板中主要是对当前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;
    }
}
数据结构与算法

关于作者

Kirago
个人站点 https://kiragoo.github.io/
获得点赞
文章被阅读