Leetcode 129求根节点到叶节点数字之和、104二叉树的最大深度、8字符串转换整数(atoi)、82删除排序链表中的重复元素II、204二分查找、94二叉树的中序遍历、144二叉树的前序遍历

Top1：Leetcode 129求根节点到叶节点数字之和

官方题解：https://leetcode.cn/problems/sum-root-to-leaf-numbers/solution/qiu-gen-dao-xie-zi-jie-dian-shu-zi-zhi-he-by-leetc/
题目描述：
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

深度优先搜索。从根节点开始，遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到数字之和，使用sum = prevSum*10+root.val。如果当前节点不是叶子节点，则计算其子节点对应的数字，然后对子节点递归遍历。

• 时间复杂度：O（n）。其中 n 是二叉树的节点个数。对每个节点访问一次。
• 空间复杂度：O（n）。空间复杂度主要取决于递归调用的栈空间，递归栈的深度等于二叉树的高度，最坏情况下，二叉树的高度等于节点个数，空间复杂度为 O(n)。

可通过完整代码：

public int sumNumbers(TreeNode root) {
    
    return dfs(root, 0);
}

private int dfs(TreeNode root, int prevSum) {
    
    if (root == null) return 0;
    int sum = prevSum * 10 + root.val;
    if (root.left == null && root.right == null) return sum;
    else return dfs(root.left, sum) + dfs(root.right, sum);
}

Top2：Leetcode 104二叉树的最大深度

官方题解：https://leetcode.cn/problems/maximum-depth-of-binary-tree/solution/er-cha-shu-de-zui-da-shen-du-by-leetcode-solution/
题目描述：
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

一、深度优先搜索。return Math.max(lH, rH) + 1;

• 时间复杂度：O（n）。其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。
• 空间复杂度：O（height）。其中 height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。【递归函数在递归过程中要给每一层递归函数分配栈空间】

可通过过完整代码：

public int maxDepth(TreeNode root) {
    
    if (root == null) return 0;
    int lH = maxDepth(root.left);
    int rH = maxDepth(root.right);
    return Math.max(lH, rH) + 1;
}

Top3：Leetcode 8字符串转换整数(atoi)

官方题解：https://leetcode.cn/problems/string-to-integer-atoi/solution/zi-fu-chuan-zhuan-huan-zheng-shu-atoi-by-leetcode-/
题目描述：
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

• 读入字符串并丢弃无用的前导空格
• 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
• 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
• 如果整数数超过 32 位有符号整数范围 [−2^31, 2^31 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
  返回整数作为最终结果。

注意：
本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。

一、自动机。建立表格照抄start、signed、in_number、end，自动机表格如下：

• start遇到谁都是都是谁
• signed和in_number只有遇到in_number不是end
  

get函数如下只有遇到in_number和signed才修改ans和sign的状态：

public void get(char c) {
    
        state = table.get(state)[get_col(c)];
        if ("in_number".equals(state)) {
    
            ans = ans * 10 + c - '0';
            ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);   // 截断整数2^31-1，-2^31
        } else if ("signed".equals(state)) {
    
            sign = c == '+' ? 1 : -1;
        }

    }

二、主函数使用for循环把每个字符送入automation.get()中，最后返回sign和ans属性的乘积

• 时间复杂度：O（n）。我们使用for循环处理所有的字符，字符长度为n
• 空间复杂度：O（1）。自动机的状态只需要常数空间存储。

可通过完整代码：

class Solution {
    
    public int myAtoi(String str) {
    
        Automaton automaton = new Automaton();
        int length = str.length();
        for (int i = 0; i < length; i++) {
    
            automaton.get(str.charAt(i));
        }
        return (int) (automaton.sign * automaton.ans);
    }
}
class Automaton {
    
    public int sign = 1;
    public long ans = 0;
    private String state = "start";
    private Map<String, String[]> table = new HashMap<String, String[]>() {
    
        {
    
            put("start", new String[] {
    "start", "signed", "in_number", "end"});
            put("signed", new String[] {
    "end", "end", "in_number", "end"});
            put("in_number", new String[] {
    "end", "end", "in_number", "end"});
            put("end", new String[] {
    "end", "end", "end", "end"});
        }
    };

    public void get(char c) {
    
        state = table.get(state)[get_col(c)];
        if ("in_number".equals(state)) {
    
            ans = ans * 10 + c - '0';
            ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);   // 截断整数2^31-1，-2^31
        } else if ("signed".equals(state)) {
    
            sign = c == '+' ? 1 : -1;
        }

    }

    private int get_col(char c) {
    
        if (c == ' ') return 0;
        if (c == '+' || c == '-') return 1;
        if (Character.isDigit(c)) return 2;
        return 3;
    }
}

Top4：Leetcode 82删除排序链表中的重复元素II

官方题解：https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/solution/shan-chu-pai-xu-lian-biao-zhong-de-zhong-oayn/
题目描述：
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

一次遍历。使用哑节点，然后从前往后遍历，遇到==的使用cur.next = cur.next.next删除。例如[1, 1, 2, 3]输出结果为[2, 3]

• 时间复杂度：O（n）。
• 空间复杂度：O（1）

可通过完整代码：

public ListNode deleteDuplicates(ListNode head) {
    
    if (head == null) return head;
    ListNode dummy = new ListNode(0, head);
    ListNode cur = dummy;
    while (cur.next != null && cur.next.next != null) {
       // 加入有一个元素直接返回了；假如有1-->1两个重复元素，直接next和next.next就都指向1了；
        // 由此地推从前往后是成立的
        if (cur.next.val == cur.next.next.val) {
    
            int x = cur.next.val;
            while (cur.next != null && cur.next.val == x) cur.next = cur.next.next;   // 这里是删除cur.next比较方便。
            // 这里是所有重复的都会被删除，例如[1, 1, 2, 3]输出[2, 3]
        } else {
    
            cur = cur.next;
        }
    }
    return dummy.next;
}

Top5：Leetcode 204二分查找

官方题解：https://leetcode.cn/problems/binary-search/solution/er-fen-cha-zhao-by-leetcode-solution-f0xw/
题目描述：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

针对排序好的数组。使用l<=r的模板，当l=r的时候就找到了结果，如果没有找到就会跳出while返回-1

• 时间复杂度：O（logn）。
• 空间复杂度：O（1）

可通过完整代码：

public int search(int[] nums, int target) {
    
    int l = 0, r = nums.length -  1;
    while (l <= r) {
       // 如果单个[a]=target，就直接返回。如果单个不是就会退出返回-1。 // 如果偶数[a=0, b=1]不超区间的时候也能找到b=target=1，奇数也是一样
        int mid = (r - l) / 2 + l;   // 等价于(l + r) / 2，但是这个一般不会超范围
        int num = nums[mid];
        if (num == target) return mid;
        else if (num < target) l = mid + 1;   // 要使区间趋向target，调整 l 范围
        else r = mid - 1;
    }
    return -1;
}

Top6：Leetcode 94二叉树的中序遍历

官方题解：https://leetcode.cn/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
题目描述：

使用递归。先一直递归到最左

• 时间复杂度：O（n）。其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
• 空间复杂度：O（n）。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

可通过完整代码：

public List<Integer> inorderTraversal(TreeNode root) {
    
    List<Integer> ans = new ArrayList<>();
    dfs(root, ans);
    return ans;
}

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

Top7：Leetcode 144二叉树的前序遍历

官方题解：
https://leetcode.cn/problems/binary-tree-preorder-traversal/solution/er-cha-shu-de-qian-xu-bian-li-by-leetcode-solution/
题目描述：

递归。前序遍历为根左右，先加入，接着逐渐往左递归

• 时间复杂度：O（n）
• 空间复杂度：O（n）

可通过完整代码：

public List<Integer> preorderTraversal(TreeNode root) {
    
    List<Integer> ans = new ArrayList<>();
    preorder(root, ans);
    return ans;
}

private void preorder(TreeNode root, List<Integer> ans) {
    
    if (root == null) {
    
        return;
    }
    ans.add(root.val);
    preorder(root.left, ans);
    preorder(root.right, ans);
}