Leetcode刷题日记

[toc]

前言：

    仅仅用于个人归档,不然不清楚自己一天到底在干什么?(**没有成就感**)所以搞了这个,我是分类来刷的题目，不懂的我才会去补薄弱的知识点。

深度优先遍历(2022-03-29——未定)

[HTML_REMOVED]

2022-03-29

二叉树的中序遍历

题目内容：给出一个二叉树，求它的中序序列

思路：按照中序序列的定义，先左，再中，再右，就可以求得

代码：

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new LinkedList<>();
            if (root == null)
                return res;
            res.addAll(inorderTraversal(root.left));
            res.add(root.val);
            res.addAll(inorderTraversal(root.right));
            return res;
        }
    }

时间复杂度:$O(n)$

验证二叉搜索树

题目内容：给你一颗二叉树，判断是否是一个二叉搜索树

思路：根据定义来做，但是如何将以前的值保存下来是一个问题，我们只要给出一个上界和一个下届就可以进行判断，如果有越界的一定不是二叉搜索树了。

代码：

class Solution {
        public boolean isValidBST(TreeNode root) {
            //题目中无空的节点，保证没有空的存在
            //我的获得每个根节点的值,然后把值传给左右子树不断得去判断，知道左右子树为空，就返回true，
            //如果不满足就返回false

            return check(root,Long.MIN_VALUE,Long.MAX_VALUE);
        }
        public boolean check(TreeNode root,long min,long max){
            if (root==null)
                return true;
            if (root.val<=min||root.val>=max)
                return false;
            return check(root.left,min,root.val)&&check(root.right,root.val,max);
        }
    }

时间复杂度:$O( n )$

相同的树

题目内容：判断两棵树的结构和值是否完全一致

思路：如果完全相同，那么相应节点的情况也一定相同，首先要保证节点都存在且值都相同。

代码：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p==null && q==null)
            return true;
        if (p==null&&q!=null)
            return false;
        if (p!=null&&q==null)
            return false;
        if (p.val!=q.val)
            return false;
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}