牛客每日刷题之二叉树

目录

题目

思路1

思路2

题解1

 题解2

复杂度

📃结语

---

✅作者简介：我是18shou，一名即将秋招的java实习生

✨个人主页：_18shou

🔥系列专栏：牛客刷题专栏

📃推荐一款模拟面试、刷题神器👉 在线刷题面经模拟面试

题目

描述
给定一个二叉树根节点，请你判断这棵树是不是二叉 搜索树。
二叉搜索树满足每个节点的左子树上的所有节点均严格小于当前节点且右子树上的所有节点均严格大于当前节点。

 

思路1

知识点1:二叉树递归
递归是一个过程 或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复 杂的问题层层转化为一个与原问题相似的规模较
小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。
而二又树的递归，则是将某个节点的左子树、右子树看成一颗完整的树， 那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因
此可以自我调用函数不断进入子树。

思路2

知识点:栈
栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶， 另-端被称为栈底。 元素入栈指的是把新元素放到栈顶元素的上面，使
之成为新的栈顶元素;元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
思路:
我们也可以利用栈来代替递归。如果-棵二 叉树， 对于每个根节点都优先访问左子树，那结果是什么?从根节开始不断往左，第-个被访问的肯
定是最左边的节点，然后访问该节点的右子树，最后向上回到父问题。因为每次访问最左的元素不止对一整棵二叉树成立，而是对所有子问题都成
立,因此循环的时候自然最开始都是遍历到最左:
//直到没有左节点

 
while(head != null){
s. push(head);
}

head = head.1eft;
然后访问，然后再进入右子树，我们可以用栈来实现回归父问题。
具体做法:
●step 1:优先判断树是否为空,空树不遍历。
●step 2:准备一个数组记录中序遍历的结果。
●step3: 准备辅助栈，当二-叉树节点为空了且栈中没有节点，我们就停止访问。
●step 4:从根节点开始，每次优先进入每棵的子树的最左边一 个节点，我们将其不断加入栈中，用来保存父问题。
●step 5:到达最左后，可以开始访问，如果它还有右节点，则将右边也加入栈中，之后右子树的访问也是优先到最左。
不
●step6: 遍历数组，依次比较相邻两个元素是否为递增序。
TOP

题解1

import java.util.*;
public class Solution {
    int pre = Integer.MIN_VALUE;
    //中序遍历
    public boolean isValidBST (TreeNode root) { 
        if (root == null)
            return true;
        //先进入左子树
        if(!isValidBST(root.left)) 
            return false;
        if(root.val < pre)
            return false;
        //更新最值
        pre = root.val;
        //再进入右子树
        return isValidBST(root.right); 
    }
}

 题解2

import java.util.*;
public class Solution {
    public boolean isValidBST(TreeNode root){
        //设置栈用于遍历
        Stack s = new Stack(); 
        TreeNode head = root;
        //记录中序遍历的数组
        ArrayList sort = new ArrayList(); 
        while(head != null || !s.isEmpty()){
            //直到没有左节点
            while(head != null){   
                s.push(head);
                head = head.left;
            }
            head = s.pop();
            //访问节点
            sort.add(head.val); 
            //进入右边
            head = head.right; 
        }
        //遍历中序结果
        for(int i = 1; i < sort.size(); i++){ 
            //一旦有降序，则不是搜索树
            if(sort.get(i - 1) > sort.get(i)) 
                return false;
        }
        return true;
    }
}

 

复杂度

时间：O（N）

空间：O（N）

📃结语

兄弟们，一起来刷题👉嘎嘎的写题