《LeetCode热题100》笔记题解思路技巧优化_Part

《LeetCode热题100》笔记&题解&思路&技巧&优化_Part_4

😍😍😍 相知
🙌🙌🙌 相识
😢😢😢 开始刷题
- 二叉树
- - 🟢1. 二叉树的中序遍历
  - 🟢2. 二叉树的最大深度
  - 🟢3. 翻转二叉树
  - 🟢4. 对称二叉树
  - 🟢5. 二叉树的直径
  - 🟡6. 二叉树的层序遍历
  - 🟢7. 将有序数组转换为二叉搜索树
  - 🟡8. 验证二叉搜索树
  - 🟡9. 二叉搜索树中第K小的元素
  - 🟡10. 二叉树的右视图
  - 🟡11. 二叉树展开为链表
  - 🟡12. 从前序与中序遍历序列构造二叉树
  - 🟡13. 路径总和II
  - 🟡14. 二叉树的最近公共祖先
  - 🔴15. 二叉树中的最大路径和

在这里插入图片描述

😍😍😍 相知

刷题不要一上来就直接干，先看题，明白题说的什么意思，然后想一下用什么现成的算法和数据结构可以快速解决，如果还是无从下手，建议先去看视频，不要直接翻评论或官方代码实现，看完视频，自己在idea中模拟敲几遍代码，如果跑通了，先别急着上leetcode黏贴，而是再回顾一下要点，然后确定自己完全懂了后，在leetcode中手敲，注意是手敲下来！！！目前我就是采用的这种方法，虽然慢，但是可以维持一周忘不掉它，如果要想长期不忘，只能隔段时间就review一下了，就算是大牛，知道方法，长时间不碰，也不可能保证一次到位把代码敲完一遍过！！！

🙌🙌🙌 相识

刷LeetCode热题100的想法有几个原因：

流行度高：LeetCode是一个广受欢迎的在线刷题平台，拥有大量用户和活跃的讨论社区。因此，热门题目通常代表了大多数人认为重要的题目或者面试中常见的题目。
面试备战：LeetCode上的题目往往和面试题目有很大的重合度。刷LeetCode热题100可以帮助你熟悉常见的面试题型和解题思路，提高应对面试的能力。
广泛的覆盖：热题100覆盖了各种难度级别的题目，包括简单、中等和困难。通过解答这些题目，可以提高自己的算法和编程能力，并扩展自己的知识面。
反馈和讨论：由于热题100是根据用户的反馈和讨论度排名的，因此这些题目往往有大量的解题思路和讨论可以参考。你可以从其他人的解题过程中学习到很多知识和技巧。

😢😢😢 开始刷题

二叉树

🟢1. 二叉树的中序遍历

题目链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/description/?envType=study-plan-v2&envId=top-100-liked

这个必会！包括前序遍历、后序遍历

方法1：通用迭代法

我们还可以采用通用的迭代法来完成前中后序遍历。具体思想如下：

我把所有元素按照我要处理的顺序依次入栈就行，入栈前要判断必须是非空节点，这样再出栈的时候就保证了遍历的顺序是满足我们前中后序要求的。
怎么实现依次入栈呢？只有每次弹出当前栈顶的中节点，再根据将这个中节点和它的左右孩子按顺序入栈，才能实现按要求依次入栈。
我们只处理‘中节点’，把每次弹出的‘中节点’的值加入数组中。注意这个中节点其实指代的是所有节点，因为所有的子节点都是他们自己子节点的中节点。
我们需要在处理中节点的前面加一个标识符null，一旦栈弹出来null，我们就可以知道下一个弹出的节点需要我们处理（存值），这也是之前为什么不允许空节点入栈的原因。

/**
 * 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<>();
        if(root==null)return list;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode temp = stack.peek();
            if(temp!=null){
                stack.pop();
                if(temp.right!=null) stack.push(temp.right);
                stack.push(temp);
                stack.push(null);
                if(temp.left!=null) stack.push(temp.left);
            }
            else{
                stack.pop();
                list.add(stack.pop().val);
            }
        }
        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<>();
        inorderdigui( root,list);
        return list;
    }
    public void inorderdigui(TreeNode root,List<Integer> list){
        if(root==null)return;
        if(root.left!=null) inorderdigui(root.left,list);
        list.add(root.val);
        if(root.right!=null) inorderdigui(root.right,list);
    }
}

🟢2. 二叉树的最大深度

题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/?envType=study-plan-v2&envId=top-100-liked

可以利用层序遍历一共多少层就是多深

/**
 * 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 depth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(null);
        while(!queue.isEmpty()){
            TreeNode temp = queue.peek();
            if(temp!=null){
                queue.poll();
                if(temp.left!=null)queue.add(temp.left);
                if(temp.right!=null)queue.add(temp.right);
            }
            else{
                queue.poll();
                depth++;
                if(!queue.isEmpty())queue.add(null);
            }
        }
        return depth;
    }
}

递归
Math.max（左边最深的+1，右边最深的+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 int maxDepth(TreeNode root) {
        if(root==null)return 0;
        int depth = 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}

🟢3. 翻转二叉树

题目链接：https://leetcode.cn/problems/invert-binary-tree/?envType=study-plan-v2&envId=top-100-liked

在这里插入图片描述

/**
 * 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  root;
        TreeNode left = root.left;
        root.left = invertTree(root.right);
        root.right  = invertTree(left);
        return root;

    }
}

🟢4. 对称二叉树

题目链接：https://leetcode.cn/problems/symmetric-tree/?envType=study-plan-v2&envId=top-100-liked

/**
 * 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 check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

/**
 * 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;
        if(root.left==null&&root.right==null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root.left);queue.add(root.right);
        while(!queue.isEmpty()){
            TreeNode lefttree = queue.poll();
            TreeNode righttree = queue.poll();
            if(lefttree==null&&righttree==null) continue;
            if(lefttree==null&&righttree!=null)return false;
            if(lefttree!=null&&righttree==null)return false;
            if(lefttree.val!=righttree.val)return false;
            
            queue.add(lefttree.left);
            queue.add(righttree.right);
            queue.add(righttree.left);
            queue.add(lefttree.right);


            
        }
        return true;
    }
}

🟢5. 二叉树的直径

题目链接：https://leetcode.cn/problems/diameter-of-binary-tree/?envType=study-plan-v2&envId=top-100-liked

/**
 * 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 diameterOfBinaryTree(TreeNode root) {
        if(root==null)return 0;
        int left = getdept(root.left);
        int right = getdept(root.right);
        int temp = left+right;
        return Math.max(Math.max(temp,diameterOfBinaryTree(root.left)),diameterOfBinaryTree(root.right));
    }
     public int getdept (TreeNode root){
        if(root == null)return 0;
        int left = getdept(root.left);
        int right = getdept(root.right);
        return Math.max(left,right)+1;
    }
}

🟡6. 二叉树的层序遍历

题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/?envType=study-plan-v2&envId=top-100-liked

/**
 * 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) {
        List<List<Integer>> result = new ArrayList();
        if(root==null)return result;
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            int a = queue.size();
            List<Integer> list = new ArrayList();
            for(int i = 0;i<a;i++){
                TreeNode temp  = queue.peek();
                list.add(temp.val);
                queue.poll();
                if(temp.left!=null)queue.offer(temp.left);
                if(temp.right!=null)queue.offer(temp.right);
            }
            result.add(list);
        }
        return result;
    }
}

🟢7. 将有序数组转换为二叉搜索树

题目链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked

/**
 * 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 sortedArrayToBST(int[] nums) {
        if(nums.length==0)return new TreeNode();
        TreeNode result = sorted(nums,0,nums.length-1);
        return result;
    }
    public TreeNode sorted(int[] nums,int a,int b){
        if(b<a)return null;
        int mid = (b-a)/2+a;
        TreeNode result = new TreeNode(nums[mid]);
        result.left = sorted(nums,a,mid-1);
        result.right= sorted(nums,mid+1,b);
        return result;
    }
}

🟡8. 验证二叉搜索树

题目链接：https://leetcode.cn/problems/validate-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked

要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。

有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

/**
 * 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 {
    List<Integer> list = new ArrayList<>();
    private void traversal(TreeNode root){
        if(root==null)return;
        traversal(root.left);
        list.add(root.val);
        traversal(root.right);
    }
    public boolean isValidBST(TreeNode root) {
        traversal(root);
        for (int i = 1; i < list.size(); i++) {
            // 注意要小于等于，搜索树里不能有相同元素
            if (list.get(i) <= list.get(i-1)) return false;
        }
        return true;
    }
}

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

题目链接：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/?envType=study-plan-v2&envId=top-100-liked

/**
 * 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 {
    List<Integer> list = new ArrayList<>();
    private void traversal(TreeNode root){
        if(root==null)return;
        traversal(root.left);
        list.add(root.val);
        traversal(root.right);
    }
    public int kthSmallest(TreeNode root, int k) {
        traversal(root);
        return list.get(k-1);
    }
}

🟡10. 二叉树的右视图

题目链接：https://leetcode.cn/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=top-100-liked

/**
 * 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) {
        if(root==null)return new ArrayList();
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        int temp = 0;
        queue.add(root);
        queue.add(null);
        while(!queue.isEmpty()){
            TreeNode tree= queue.poll(); 
            if(tree!=null){
                if(tree.left!=null) queue.add(tree.left);
                if(tree.right!=null) queue.add(tree.right);
                temp = tree.val;
            }
            else{
                list.add(temp);
                if(!queue.isEmpty())queue.add(null);
            }
            
        }
        return list;
    }
}

🟡11. 二叉树展开为链表

题目链接：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-100-liked

/**
 * 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 void flatten(TreeNode root) {
        if(root==null)return;
        TreeNode result = root;
        while(root.left!=null||root.right!=null){
            TreeNode right = root.right;
            TreeNode left = root.left;
            if(left!=null){
                TreeNode temp = left;
                while(left.right!=null){
                    left = left.right;
                }
                left.right = right;
                root.left = null;
                root.right = temp;
            }else{
               root =  root.right;
            }
        }
        root =  result;
    }
}

🟡12. 从前序与中序遍历序列构造二叉树

题目链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/?envType=study-plan-v2&envId=top-100-liked

/**
 * 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) {
        if(preorder.length==0)return new TreeNode();
        TreeNode result = new TreeNode (preorder[0]);
        int mid = 0;
        for(int i = 0;i<inorder.length;i++){
            if(inorder[i]==preorder[0]){
                mid = i;
                break;
            }
        }
        result.left = solve(preorder,inorder,0,mid-1,1);
        result.right = solve(preorder,inorder,mid+1,inorder.length-1,mid+1);
        return result;
    }
    public TreeNode solve(int [] preorder,int [] inorder,int l,int r,int ll){
        if(ll>=preorder.length)return null;
        if(r<l)return null;
        TreeNode result = new TreeNode (preorder[ll]);
        int mid = l;
        for(int i = l;i<=r;i++){
            if(inorder[i]==preorder[ll]){
                mid = i;
                break;
            }
        }
        result.left = solve(preorder,inorder,l,mid-1,ll+1);
        result.right = solve(preorder,inorder,mid+1,r,ll+mid-l+1);
        return result;
    }
}

🟡13. 路径总和II

题目链接：https://leetcode.cn/problems/path-sum-iii/description/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }

        long ret = rootSum(root, targetSum);
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return (int)ret;
    }

    public long rootSum(TreeNode root, long targetSum) {
        long ret = 0;

        if (root == null) {
            return 0;
        }
        int val = root.val;
        if (val == targetSum) {
            ret++;
        } 

        ret += rootSum(root.left, targetSum - val);
        ret += rootSum(root.right, targetSum - val);
        return ret;
    }
}

🟡14. 二叉树的最近公共祖先

题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||p==root||q==root) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left!=null&&right!=null)return root;
        else if(left!=null)return left;
        else return right;
    }
}

🔴15. 二叉树中的最大路径和

题目链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=study-plan-v2&envId=top-100-liked

/**
 * 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 {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }
    public int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = Math.max(0, dfs(root.left));
        int rightMax = Math.max(0, dfs(root.right));
        max = Math.max(max, (root.val + leftMax + rightMax));
        return root.val + Math.max(leftMax, rightMax);
    }
}