编程导航会员会员
登录/注册

力扣刷题Hot100

昨晚回学校，好久没跟同学出去玩了，网吧四连坐去了，忘记发刷题进度了。哈哈哈

  1. 94. 二叉树的中序遍历 - 力扣（LeetCode）
  2. 104. 二叉树的最大深度 - 力扣（LeetCode）
  3. 226. 翻转二叉树 - 力扣（LeetCode）
  4. 101. 对称二叉树 - 力扣（LeetCode）
  5. 543. 二叉树的直径 - 力扣（LeetCode）
  6. 102. 二叉树的层序遍历 - 力扣（LeetCode）
  7. 108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
  8. 98. 验证二叉搜索树 - 力扣（LeetCode）
  9. 230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）
  10. 199. 二叉树的右视图 - 力扣（LeetCode）
  11. 114. 二叉树展开为链表 - 力扣（LeetCode）
  12. 105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

中序遍历

经典题了...

两种解法

解法一：递归法

▼
java
复制代码
/**
 * 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> ans = new ArrayList<>();
        inorderTraversal(root,ans);
        return ans;
    }
    public void inorderTraversal(TreeNode root, List<Integer> ans) {
        if (root == null){
            return;
        }
        inorderTraversal(root.left,ans);
        ans.add(root.val);
        inorderTraversal(root.right,ans);
        return;
    }
}

解法一 迭代法：

▼
java
复制代码
/**
 * 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> ans = new ArrayList<>();
        Deque<TreeNode> q = new ArrayDeque<>();
        while (root != null || !q.isEmpty()){
            while (root != null){
                q.addLast(root);
                root = root.left;
            }
            root = q.removeLast();
            ans.add(root.val);
            root = root.right;
        }
        return ans;
    }
}

最大深度

左右递归再比较

▼
java
复制代码
/**
 * 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 int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        return Math.max(l,r) + 1;
    }
}

反转二叉树

中序，先反转，再遍历

▼
java
复制代码
/**
 * 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 TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

对称二叉树

分开两颗树左右遍历

▼
java
复制代码
/**
 * 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) {
        return isSymmetric(root.left,root.right);
    }

    private boolean isSymmetric(TreeNode p , TreeNode q){
        if (p == null || q == null){
            return q == p;
        }
        return q.val == p.val && isSymmetric(p.left , q.right) && isSymmetric(p.right, q.left);
    }
}

二叉树直径

最大深度类型，每个节点都可以是直径的中间节点，每次放回节点的左右最大的长度

▼
java
复制代码
/**
 * 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 {
    private int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode root){
        if (root == null){
            return 0;
        }
        int l = dfs(root.left);
        int r = dfs(root.right);
        ans = Math.max(ans, l + r);
        return Math.max(l , r)  +1;
    }
}

层序遍历

板子题....直接默写

▼
java
复制代码
/**
 * 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<List<Integer>> levelOrder(TreeNode root) {
        if (root == null){
            return List.of();
        }
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()){
            int n = q.size();
            List<Integer> vals = new ArrayList<>();
            while (n -- > 0){
                TreeNode node = q.poll();
                vals.add(node.val);
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            ans.add(vals);
        }
        return ans;
    }
}

将有序数组转化为二叉搜索树

有序 + 中序

▼
java
复制代码
/**
 * 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 {
    private int[] nums;
    public TreeNode sortedArrayToBST(int[] nums) {
        this.nums = nums;
        return dfs(0,nums.length - 1);
    }

    private TreeNode dfs(int l , int r){
        if (l > r){
            return null;
        }
        int m =  l + r >> 1;
        return new TreeNode(nums[m],dfs(l, m - 1),dfs(m + 1, r));
    }
}

验证二叉搜索树

根据二叉树的性质，每个节点的取值都有个严格的区间

▼
java
复制代码
/**
 * 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 dfs(root,Long.MIN_VALUE, Long.MAX_VALUE);       
    }

    private boolean dfs(TreeNode root , long l , long r){
        if (root == null){
            return true;
        }
        long x = root.val;
        return l < x && x < r && dfs(root.left,l,x) && dfs(root.right , x ,r);
    }
}

二叉搜索树中第K小的元素

中序迭代模板稍微改一点

▼
java
复制代码
/**
 * 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 int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> q = new ArrayDeque<>();
        while (!q.isEmpty() || root != null){
            while (root != null){
                q.addLast(root);
                root = root.left;
            }
            root = q.removeLast();
            k --;
            if (k == 0){
                return root.val;
            }
            root = root.right;
        }
        return -1;
    }
}

二叉树的右视图

中序，但中右左

▼
java
复制代码
/**
 * 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> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root,0 , ans);
        return ans;       
    }

    private void dfs(TreeNode root , int depth , List<Integer> ans){
        if (root == null){
            return;
        }
        if (depth == ans.size()){
            ans.add(root.val);
        }
        dfs(root.right,depth + 1, ans);
        dfs(root.left, depth + 1,ans);
    }
}

二叉树展开为链表

使用头插法，需要一个额外的指针head，右左中遍历

推荐题解：114. 二叉树展开为链表 - 力扣（LeetCode）

▼
java
复制代码
/**
 * 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 {
    private TreeNode head;
    public void flatten(TreeNode root) {
        if (root == null){
            return;
        }
        flatten(root.right);
        flatten(root.left);
        root.left = null;
        root.right = head;
        head = root;
    }
}

从前序与中序遍历构造二叉树

板子题了...

▼
java
复制代码
/**
 * 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 TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        if ( n == 0){
            return null;
        }   
        int size  = indexOF(inorder,preorder[0]);
        int[] pre1 = Arrays.copyOfRange(preorder,1,1+size);
        int[] pre2 = Arrays.copyOfRange(preorder,1 + size , n);
        int[] in1 = Arrays.copyOfRange(inorder,0,size);
        int[] in2 = Arrays.copyOfRange(inorder,size + 1,n);
        return new TreeNode(preorder[0],buildTree(pre1,in1),buildTree(pre2,in2));
    }

    private int indexOF(int[] a , int x){
        for (int i = 0 ; ;i ++){
            if (a[i] == x){
                return i;
            }
        }
    }
}
算法
Java
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
quan
quan
等级
内容推荐
更多
LEO 卫星星座管理平台
4
新手SpringSecurity6.0源码流程总结
3
🛰️ dtSpaceMap - 实时卫星追踪 3D 可视化平台
5
Spring Boot 如何处理跨域请求（CORS）：深度调研报告
3
#字节内推# 实习、校招、社招均有岗位
4
作者分享
更多
来上海啦，有没有租房的推荐哇，在徐汇区上班，酒店太贵了🤑。
4
好久没冒泡了，力扣热题100题分享也停更好久了。 但是也没浪费这段时间，这段时间总体是玩+面试+毕设。结果总体毕设差不多了，以及拿到了游族网络的实习offer，年后入职，java和kotlin，说是有转正机会。说实话还是有点犹豫的，因为后面有春招，我怕实习冲突，毕竟也不可能说把机会全压在这一个公司。然后又想去试试，毕竟也算是个国内比较大的游戏公司了，再刷个实习经历简历试试。 唉，这个就业形势，双非仔真的很难哦，我都开始做两手准备，测开，真的我这段时间也在看这方面的知识，我后面投大厂春招的话，真的会all in测开了碰碰运气了，java做第二手中厂或者游戏公司的准备。 我不喜欢说大话（社恐bushi）也没啥大目标，毕竟自己的实力和背景在这，所以我认为这也是我看的很开的原因，有份工作就不错了。。。说实话我还是这一届学院第一个有正儿八经的符合专业方向的应届生，然后总共也没几个有实习经历，有不少都去了学校合作的培训机构学游戏和嵌入式了，然后放弃秋招，直接春招，我看不懂。我玩的好的室友也是学游戏，然后让他年后来上海游族网络投递找我玩，哈哈哈。 不知不觉又写了怎么多，大家觉得我的年后安排合理吗（边实习边春招），大家可以分享一下自己的经历让我参考参考。😜 tips:上海租房好贵哦，公司在徐汇区，有推荐的嘛？
3
泛微网络深圳三面结束，挂了。。。。麻了，聊的挺好的啊，可能是我薪资要高了？？？不会吧，我问过朋友的，也有可能是我说我比较介意二开，更喜欢做新项目，太操蛋了，挂了，直接拉黑，没一点反馈。。。。 算了，反正也没什么意愿，因为做的业务不喜欢。 卧槽，成都的MOKA刚刚来电话了，周三面试，实习转正岗位（这又是什么时候投的？🤣） 转正9k * 15。 兄弟们这薪资怎么说？？？ 我先接面试试试我的技术水平吧。
2
力扣刷题Hot100
2
泛微网络实习面经
3
下载 APP