AI 助理
备案控制台
开发者社区 人工智能 文章 正文

HOT 100（21~40）【LeetCode】4

2023-08-24 46
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： HOT 100（21~40）【LeetCode】4

94. 二叉树的中序遍历【 简单】

94.二叉树的中序遍历

简单

1.9K

相关企业

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]

提示：

树中节点数目在范围 [0, 100] 内

-100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归中序

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        inorder(root,list);
        return list;
    }
    public void inorder(TreeNode root,List<Integer> list){
         if(root!=null){
            inorder(root.left,list);
            list.add(root.val);
            inorder(root.right,list);
        }
    }
}

非递归中序1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){//当前结点指针及栈均空,则结束
            while(cur!=null){//访问根结点,根指针进栈,进入左子树
                stack.push(cur);
                cur=cur.left;
            }
            if(!stack.isEmpty()){
                cur=stack.pop();
                list.add(cur.val);
                cur=cur.right;//根指针退栈,进入其右子树
            }
        }
        return list;
    }
}

非递归中序2

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){//当前结点指针及栈均空,则结束
            if(cur!=null){//访问根结点,根指针进栈,进入左子树
                stack.push(cur);
                cur=cur.left;
            }
            else{
                cur=stack.pop();
                list.add(cur.val);
                cur=cur.right;//根指针退栈,进入其右子树
            }
        }
        return list;
    }
}

96. 不同的二叉搜索树【中等】

96.不同的二叉搜索树

中等

2.3K

相关企业

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1

提示：

1 <= n <= 19

官方

class Solution {
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }
}

98. 验证二叉搜索树

  1. 验证二叉搜索树
    中等
    2.1K
    相关企业
    给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。

节点的右子树只包含 大于 当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104] 内

-231 <= Node.val <= 231 - 1

参考

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean isValidBST(TreeNode node,long lower,long upper) {
        if(node==null){
            return true;
        }
        if(node.val<=lower||node.val>=upper){
            return false;
        }
        return isValidBST(node.left,lower,node.val)&&isValidBST(node.right,node.val,upper);
    }
}

101. 对称二叉树【简单】

101.对称二叉树

简单

2.5K

相关企业

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

树中节点数目在范围 [1, 1000] 内

-100 <= Node.val <= 100

利用相似性like

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        TreeNode leftTree=root.left;
        TreeNode rightTree=root.right;
        return like(leftTree,rightTree);
    }
    public boolean like(TreeNode t1,TreeNode t2){
        boolean like1,like2;
        if(t1==null&&t2==null) return true;
        if(t1==null||t2==null) return false;
        if(t1.val==t2.val) {
            TreeNode l1=t1.left;
            TreeNode r1=t1.right;
            TreeNode l2=t2.left;
            TreeNode r2=t2.right;
            like1=like(l1,r2);
            like2=like(l2,r1);
            return like1&&like2;
        }
        return false;
    }
}

最后

2023-7-1 12:30:19

文章标签：
算法
日星月云
目录
相关文章
日星月云
|
缓存 调度
HOT 100（导航）【LeetCode】
HOT 100（导航）【LeetCode】
日星月云
100 0
日星月云
|
调度
HOT 100（81~100）【LeetCode】4
HOT 100（81~100）【LeetCode】4
日星月云
56 0
日星月云
HOT 100（81~100）【LeetCode】3
HOT 100（81~100）【LeetCode】3
日星月云
46 0
日星月云
|
人工智能 BI 索引
HOT 100（81~100）【LeetCode】2
HOT 100（81~100）【LeetCode】2
日星月云
57 0
日星月云
|
算法 C++
HOT 100（81~100）【LeetCode】1
HOT 100（81~100）【LeetCode】1
日星月云
56 0
日星月云
|
缓存 Java 测试技术
HOT 100（41~60）【LeetCode】3
HOT 100（41~60）【LeetCode】3
日星月云
46 0
日星月云
|
存储 人工智能 算法
HOT 100（61~80）【LeetCode】1
HOT 100（61~80）【LeetCode】1
日星月云
83 0
日星月云
|
算法
HOT 100（21~40）【LeetCode】3
HOT 100（21~40）【LeetCode】3
日星月云
69 0
起飞的风筝
|
8月前
|
存储 算法
《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数
《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数
起飞的风筝
74 0
起飞的风筝
|
8月前
|
网络协议
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
起飞的风筝
120 0