Leetcode

以往刷题的很多题并没有做系统性记录，逻辑不够清晰。本页将已经刷过的每题进行二次总结，强化算法实现、逻辑思维能力。同时每天也会坚持刷题，坚持总结一篇以往AC的题目。

13. 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。

X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。

C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

import java.util.HashMap;
import java.util.Map;
/*
 * @lc app=leetcode.cn id=13 lang=java
 *
 * [13] 罗马数字转整数
 */
// @lc code=start
class Solution {
    public int romanToInt(String s) {
        /** 
         * Accepted //时间有点慢
         * 3999/3999 cases passed (10 ms)
         * Your runtime beats 24.88 % of java submissions
         * Your memory usage beats 5.56 % of java submissions (40.2 MB)
        */
        if(s == null || s.length() == 0){
            return 0;
        }
        Map<String, Integer> lib = new HashMap<>();
        lib.put("I", 1);
        lib.put("V", 5);
        lib.put("X", 10);
        lib.put("L", 50);
        lib.put("C", 100);
        lib.put("D", 500);
        lib.put("M", 1000);

        int sum = 0;
        String preSIString ="";
        for (int i = 0; i < s.length(); ++i) {
            String sI = s.substring(i, i + 1);
            sum+=lib.get(sI);

            if((sI.equals("V")  || sI.equals("X")) &&  preSIString.equals("I")  ){
                sum -=2;
            }
            else if((sI.equals( "L") || sI.equals("C")) &&  preSIString.equals("X")){
                sum -=20;
            }
            else if((sI.equals( "D") || sI.equals( "M")) &&  preSIString.equals("C")){
                sum -=200;
            }
            preSIString = sI;
        }

        return sum;
    }

    public static void main(String[] args) {
        String rom = "LVIII";

        Solution solution = new Solution();

        int ret = solution.romanToInt(rom);

        System.out.println(ret);
    }
}
// @lc code=end

解：

我们定义一个Map存储每个字符对应的数值。

根据如下信息，可以得到，在遇上I、V、X 或者 X、L、C 或者C、D、M同时出现时需要特殊处理。

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

因此，我们在遇到每个字符的时候在总数上加上一个该字符对应的数值，通过判断当前字符是否是”V、X 或者L、C 或者D、M”来进行处理特殊情况。在上述条件下，且上一个字符是对应的I、X、C，则需要减去2 * I、2 * X、2 * C，来纠正最新的数据。

最终数据的总和就是我们要的答案。

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。
1
2
输入: ["flower","flow","flight"]
输出: "fl"
1
2
3
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

package leetcode_14_longestCommonPrefix;

/*
 * @lc app=leetcode.cn id=14 lang=java
 *
 * [14] 最长公共前缀
 */

// @lc code=start
class Solution {
    /** 
     * Accepted
     * 118/118 cases passed (1 ms)
     * Your runtime beats 79.38 % of java submissions
     * Your memory usage beats 42.5 % of java submissions (37.6 MB)
    */
    public String longestCommonPrefix(String[] strs) {
        // 输入校验
        StringBuffer strPrefix = new StringBuffer();
        if(strs == null || strs.length == 0){
            return "";
        }
        if(strs.length ==1){
            return strs[0];
        }
		
        for (int i = 0; i < strs[0].length(); ++i) {
            char tmp = strs[0].charAt(i);
            // 遍历有几个字符串
            for (int j = 0; j < strs.length; ++j) {
                if (strs[j].length() == i || strs[j].charAt(i) != tmp) {
                    return strs[0].substring(0, i);
                }
            }
            strPrefix.append(tmp);
        }
        return strPrefix.toString();
    }

    public static void main(String[] args) {
        String[] strs = {"cc","c",};    
        Solution solution = new Solution();
        String prefix = solution.longestCommonPrefix(strs);
        System.out.println(prefix);

    }

}
// @lc code=end

解：

时间复杂度：log(n*m)，n代表数组长度，m代表共同前缀个数

思路:

获取第一个字符串的长度n，从0-n进行遍历，在某个下标位置记录当前字符，比较数组中剩下元素的当前位置字符是否相同。如果相同，则输出字符串附加一个字符。

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

import java.util.*;

class Solution {
    /*异常类*/
    class mException extends Exception {
        public String getCode() {
            return "new Exception";
        }
        public mException(String message) {
            super(message);
        }
    }

    public int threeSumClosest(int[] nums, int target) {

        Arrays.sort(nums);

        int len = nums.length;

        try {

            if (3 > len) {
                throw new mException("Invalid Input! Length of array < 3");
            }

            // int [] nums= {-1,2,1,-4};-4 -1 1 2
            int i = 0, startIndex = i + 1, endIndex = len - 1;

            int closestNum = nums[i] + nums[startIndex] + nums[endIndex];
            int tempNum = 0;

            for (; i < nums.length; ++i) {
                startIndex = i + 1;
                endIndex = len - 1;

                while (i != startIndex && startIndex != endIndex && i != endIndex) {
                    tempNum = nums[i] + nums[startIndex] + nums[endIndex];

                    // 计算两个数值的距离
                    if (Math.abs(target - tempNum) < Math.abs(target - closestNum)) {
                        closestNum = tempNum;
                    }

                    if (tempNum < target) {
                        startIndex++;
                    } else {
                        endIndex--;
                    }
                }

            }
            return closestNum;

        } catch (mException e) {
            // TODO: handle exception
            e.printStackTrace();
        }
        return 0;
    }
    public static void main(String[] args) {

        int[] nums = { -1, 2, 1, -4 };
        Solution so = new Solution();
        int target = 1;
        System.out.println(so.threeSumClosest(nums, target));
    }
}

解：

我们可以通过双指针的方式降低时间复杂度（前提是该数组是有序的）。

i指向当前下标，start = i+1，end = length - 1;

每次遍历，将三个下标对应的数组相加求和（temp）。记录和target距离最小的temp。

如果target < temp，end小标减一。如果target > temp，start下标加一，该过程用于找到每个i小标对应的与target相差最小的那三组数之和。

遍历完i，就得到了最接近target的三数之和。

18.最接近的四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，**b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：
1
2
3
4
5
6
7
8
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

package leetcode_18_fourSum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// @lc code=start
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<Integer> item;
        List<List<Integer>> ans = new ArrayList<>();

        Arrays.sort(nums);

        for (int a = 0; a < nums.length - Number.LastTwoIndex; ++a) {
            for (int b = a + 1; b < nums.length - 1; ++b) {
                int startIndex = b + 1;
                int endIndex = nums.length - 1;

                while (startIndex < endIndex) {
                    int tempSum = nums[a] + nums[b] + nums[startIndex] + nums[endIndex];

                    if ((tempSum - target) == 0) {
                        item = new ArrayList<>();
                        /**
                         * 需要考虑提出重复元组
                         */
                        item.add(nums[a]);
                        item.add(nums[b]);
                        item.add(nums[startIndex]);
                        item.add(nums[endIndex]);
                        if (nums[a] == 333) {
                            int breakPoint = 1;
                        }
                        if (!isExist(ans, item)) {
                            ans.add(item);
                        }

                    }

                    if (tempSum > target) {
                        endIndex--;
                    } else {
                        startIndex++;
                    }

                }
            }
        }

        return ans;
    }

    private boolean isExist(List<List<Integer>> ans, List<Integer> item) {
        boolean is = false;
        for (List<Integer> itemInList : ans) {
            boolean lastSame = false;
            for (int i = 0; i < item.size(); ++i) {

                // Java中要进行比较的，最好还是用equals。
                // 从java核心技术讲义中，如果两个Integer变量的值在区间-128到127之间，则比较结果为true
                if (item.get(i).equals(itemInList.get(i))) {
                    lastSame = true;
                } else {
                    lastSame = false;
                    break;
                }

            }
            if (lastSame) {
                return true;
            }
        }

        return is;
    }

    public static void main(String[] args) {
        /*测试*/
        int[] nums = { -497, -494, -484, -477, -453, -453, -444, -442, -428, -420, -401, -393, -392, -381, -357, -357,
                -327, -323, -306, -285, -284, -263, -262, -254, -243, -234, -208, -170, -166, -162, -158, -136, -133,
                -130, -119, -114, -101, -100, -86, -66, -65, -6, 1, 3, 4, 11, 69, 77, 78, 107, 108, 108, 121, 123, 136,
                137, 151, 153, 155, 166, 170, 175, 179, 211, 230, 251, 255, 266, 288, 306, 308, 310, 314, 321, 322, 331,
                333, 334, 347, 349, 356, 357, 360, 361, 361, 367, 375, 378, 387, 387, 408, 414, 421, 435, 439, 440, 441,
                470, 492 };
        int target = 1682;
        new Solution().fourSum(nums, target);
    }

    public static class Number {
        public static Integer LastTwoIndex = 2;
    }
}
// @lc code=end

解：

该题“最接近的四数之和”，可以通过三数之和一样的思路进行解题。三数之和把0(n^3) => 0(n^2)，在这里可以为四数之和降到 0(n^3)的时间复杂度。

一开始的两循环遍历四个数的前两个数。
后面两个数通过双指针的方式降低时间复杂度
当然，在经过测试之后会发现有重复的元组，需要进行去重。上述代码中，通过依次比较ans列表中是否有和新增加的列表相同的列表，有则不执行add操作。

20. 有效括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:
1
2
输入: "()"
输出: true
示例 2:
1
2
输入: "()[]{}"
输出: true
示例 3:
1
2
输入: "(]"
输出: false
示例 4:
1
2
输入: "([)]"
输出: false
示例 5:
1
2
输入: "{[]}"
输出: true

package leetcode_20_isValid;
/*
 * @lc app=leetcode.cn id=20 lang=java
 * [20] 有效的括号
 */
import java.util.*;
// @lc code=start
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        /**
         * 解题思路： 如果是空格则跳过 如果是左括号则放入栈 如果是有括号则找栈顶，如果是一对，则栈顶出栈。 如果不是一对，则返回false
         * 
         * 遍历完之后，如果栈里面只有空格或者为空则返回true。
         * Accepted 76/76 cases passed (3 ms) Your runtime beats 40.3 % of java
         * submissions Your memory usage beats 5.48 % of java submissions (37.8 MB)
         */
        if (s == null) {
            return false;
        }
        if (s.length() == 0) {
            return true;
        }

        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == ' ') {
                continue;
            } else if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
                stack.push(s.charAt(i));

            } else if (s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}') {
                if (stack.size() <= 0) {
                    return false; // 如果有有括号的情况，没了左括号，那么就是无效的一组
                }
                Character top = stack.peek();

                if (mEqual(top, s.charAt(i))) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if (stack.size() == 0) {
            return true;
        }
        return false;
    }
    private boolean mEqual(Character left, Character right) {
        // System.out.println(left.equals(new Character('(')));
        // System.out.println(right.equals(new Character(')')));

        if (left.equals(new Character('(')) && right.equals(new Character(')')) || left.equals('[') && right.equals(']')
                || left.equals('{') && right.equals('}')) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "]";
        boolean out = solution.isValid(s);
        System.out.println(out);
        return;
    }
}
// @lc code=end

解：

通过栈的方式完成任务，把任何左括号的类型一律入栈。

如果遇到了右括号则去栈中弹出一个字符，如果这两个括号是对应的一组则继续遍历，如果不是则返回false

如果字符串遍历完毕之后栈中还有数据，那么括号不对称返回false。

如果字符串遍历完，且栈为空，那么返回true。

148 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:
1
2
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
1
2
输入: -1->5->3->4->0
输出: -1->0->3->4->5

package leetcode148;
// @lc code=start
/**
 * Definition for singly-linked list. public class ListNode { int val; ListNode
 * next; ListNode(int x) { val = x; } }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        /**
         * O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
         */
        /**
         * 快排是二分，可以达到nlogn的复杂度，需要递归，并且遍历末尾节点比较费时间。 归并排序也是二分，可以达到nlogn的时间复杂度，同时可以达到常数复杂度。
         */

        /**
         * 输入检验
         */
        if (head == null || head.next == null) {
            return head;
        }

        // Accepted
        // 16/16 cases passed (3 ms)
        // Your runtime beats 99.19 % of java submissions
        // Your memory usage beats 10.58 % of java submissions (42.9 MB)

        ListNode newList = mergeSortListNode(head);

        return newList;
    }

    public ListNode mergeSortListNode(ListNode firstNode) {
        // 找到一个节点的位置
        if (firstNode.next == null) {
            return firstNode;
        }


        // 计算中间节点，进行递归
        ListNode midNode = findMidNode(firstNode);
        ListNode secondNode = midNode.next;
        // 把列表切断成两部分！
        midNode.next = null;

        ListNode head1 = mergeSortListNode(firstNode);
        ListNode head2 = mergeSortListNode(secondNode);
        ListNode ptr1 = head1;
        ListNode ptr2 = head2;

        /**
         * 咱们在进行合并的时候不是会遇上链表循环连接？那就解决这个问题，在查找中点的时候把他cut断就好啦！！！
         */
        ListNode newHead;
        ListNode ptrCur;
        if (ptr1.val < ptr2.val) {
            newHead = ptr1;
            ptr1 = ptr1.next;
        } else {
            newHead = ptr2;
            ptr2 = ptr2.next;
        }
        ptrCur = newHead;
        while (ptr1 != null && ptr2 != null) {
            if (ptr1.val < ptr2.val) {
                ptrCur.next = ptr1;
                ptr1 = ptr1.next;

            } else {
                ptrCur.next = ptr2;
                ptr2 = ptr2.next;
            }
            ptrCur = ptrCur.next;
        }

        if (ptr1 != null) {
            ptrCur.next = ptr1;
            ptr1 = ptr1.next;
        }

        if (ptr2 != null) {
            ptrCur.next = ptr2;
            ptr2 = ptr2.next;
        }

        return newHead;
    }

    public ListNode findMidNode(ListNode firstNode) {
        /**
         * 找中点，快慢指针！
         */
        ListNode ptr = firstNode;
        ListNode fastPtr = firstNode;

        while (fastPtr != null && fastPtr.next != null && fastPtr.next.next != null) {
            ptr = ptr.next;
            fastPtr = fastPtr.next.next;
        }

        return ptr;
    }

     public static void main(String[] args) {
     	int[] nums = { 4, 2, 1, 3, 5, 8 };
     	Solution solution = new Solution();

     	ListNode head = ListNode.createNodeList(nums);

     	solution.sortList(head);

     	System.out.println(head);
     }
}
// @lc code=end

解：

归并递归描述

依据归并排序，我们需要对数据进行不断地二分。划分到只有一个节点之后，返回阶段，在返回是对两组数据进行归并，然后进一步递归返回，再将两个数组进行按序归并，如此到递归退出就能获得有序地数据。

上面代码比较长，这里做一个解释。

由于是链表，不能直接类似于数组进行索引访问，因此需要通过快慢指针获得中间元素。findMidNode()
同时找到指针之后，在进一步递归地时候，为了使得数据能够前后分割，不会被链表的链接影响，我们需要对mid结点进行切断操作。 midNode.next = null;
当数据被划分成两个链表之后就可以进一步递归-二分。
当递归数据返回的时候，我们需要对返回的有序链表进行归并。通过辅助指针的方式，不断地往头节点按递增次序拼接结点，不断返回、拼接数据就能获得会后有序地链表了。

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

/**
 * @description: 对称二叉树 https://leetcode-cn.com/problems/symmetric-tree/description/
 * @modifyContent:
 * @author: Maple Chan
 * @date: 2020-07-18 16:09:36
 * @version: 0.0.1
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        // 思路, 广度优先遍历，用栈的方式。
        if (null == root) {
            return true;
        }
        // 迭代
        return isSymmetricCoreBfs(root.left, root.right);
    }

    public boolean isSymmetricCore(TreeNode left, TreeNode right) {
        // Accepted
        // 195/195 cases passed (0 ms)
        // Your runtime beats 100 % of java submissions
        // Your memory usage beats 28.75 % of java submissions (38 MB)

        if (null == left && null == right) {
            return true;
        }
        if (null != left && null == right) {
            return false;
        }
        if (null == left && null != right) {
            return false;
        }

        if (left.val == right.val) {
            return isSymmetricCore(left.left, right.right) && isSymmetricCore(left.right, right.left);
        }

        return false;
    }

    LinkedList<TreeNode> stack = new LinkedList<>();
    /**
     * @description 迭代的方法，用队列存数据进行两两比较。
     * @author Maple Chan
     * @date: 2020-07-18 16:07:16
     * @params 
     * @return 
     */
    public boolean isSymmetricCoreBfs(TreeNode left, TreeNode right) {
        // Accepted
        // 195/195 cases passed (1 ms)
        // Your runtime beats 30.72 % of java submissions
        // Your memory usage beats 5 % of java submissions (39.5 MB)
        if (null == left && null == right) {
            return true;
        }
        if (null != left && null == right) {
            return false;
        }
        if (null == left && null != right) {
            return false;
        }

        stack.add(left);
        stack.add(right);

        while (0 < stack.size()) {
            TreeNode node1 = stack.pop();
            TreeNode node2 = stack.pop();

            if (null == node1 && null == node2) {
                continue;
            }
            if (null == node1 || null == node2 || node1.val != node2.val) {
                return false;
            }

            stack.push(node1.left);
            stack.push(node2.right);
            stack.push(node1.right);
            stack.push(node2.left);

        }

        return true;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);
        root.right = new TreeNode(2);

        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);

        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);

        Solution solution = new Solution();

        boolean ret = solution.isSymmetric(root);

        System.out.println(ret);
        return;
    }
}

解：

递归

如果镜像对称，那么左子树和右子树也一定是镜像对称。

通过递归，将左子树的左节点和右子树的右节点递归传入进行比较。

① 递归结束条件：如果左节点 == 右节点 == null，返回 ture；如果左节点 != 右节点，返回false；

②如果两个节点都不为空，且值相等，则需要进一步递归。

层序遍历

通过迭代，定义一个栈，将左节点的左子节点和右节点的右子节点，左节点的右子节点和右节点的左子节点并列放入栈中。

每次弹出两个数据：

如果两个数据相等则进一步迭代，直至栈为空返回ture。

如果两个数据不相等直接返回false

153. 寻找旋转排序数组中的最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:
1
2
输入: [3,4,5,1,2]
输出: 1
示例 2:
1
2
输入: [4,5,6,7,0,1,2]
输出: 0

题解：

/**
 * 
 * 146/146 cases passed (8 ms)
 * Your runtime beats 41.73 % of cpp submissions
 * Your memory usage beats 17.38 % of cpp submissions (8.8 MB)
 * 
*/

// @lc code=start
#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    /**
     * 用两个指针减少遍历的次数
    */
    int findMin(vector<int>& nums) {
        size_t leftPtr = 0;
        size_t rightPtr = nums.size() -1;
        size_t destinyPtr = 0;
        //cout << "debug:: in the findMin function!"<<endl;
        if(nums.size() < 1)
            cerr << "Invalid Input arry" << endl;
        if(nums.size()==1)
            return nums[0];
        
        while (nums[leftPtr] >= nums[rightPtr])
        {
            //cout << "debug:: still in the while!"<<endl;
            /* code */
            if(rightPtr - leftPtr == 1){
                //如果两个指针之差为1则说明已经找到了最小值
                destinyPtr = rightPtr;
                break;
            }
            size_t mid = (rightPtr + leftPtr) / 2;

            if(nums[mid]==nums[leftPtr] && nums[mid] == nums[rightPtr]){
                //如果三个相等没法判断的情况
                //采用顺序查找的方式
                int min = nums[0];
                
                for(size_t i=0;i<nums.size();++i){
                    if(min > nums[i]){
                        min = nums[i];
                    }
                }
                return min;
            }

            if(nums[mid] > nums[leftPtr]){
                leftPtr = mid;
            }
            if(nums[mid] < nums[rightPtr]){
                rightPtr = mid;
            }
        }
        return nums[destinyPtr];
    }
};
// @lc code=end
int main(){
    vector<int> nums = {1,2};
    Solution so;
    int min = so.findMin(nums);
    cout << min <<endl;
    return 0;
}

解：

本题是二分搜索的变题

对于传入数组，指定两个指针，一个left指针，一个right指针。

如果nums[left] >= nums[right]则说明，left指针在旋转点的左侧，right指针在旋转点的右侧。则不断进行循环，执行二分的过程。

二分的结束条件为， nums[left] > nums[right] && right-left == 1

如果nums[mid] < nums[left]说明，mid在旋转点的右侧，应该将right = mid；

如果nums[mid] > nums[right]说明，mid在旋转点的左侧，应该将left = mid；

上述代码中间还处理一个特殊情况，nums[left] == nums[mid] == nums[right]。

这种情况没法区分下一个mid应该在哪半边区域，因此用遍历的方式进行寻找nums[left] > nums[right]的位置

515. 在每个树行中找最大值

您需要在二叉树的每一行中找到最大的值。

示例：

输入:

⁠ 1

⁠ / \

⁠ 3 2

⁠ / \ \

⁠ 5 3 9

输出: [1, 3, 9]

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        // Accepted
        // 78/78 cases passed (2 ms)
        // Your runtime beats 81.33 % of java submissions
        // Your memory usage beats 7.14 % of java submissions (40.3 MB)

        // 输出检查
        List<Integer> list = new LinkedList<>();
        if (null == root) {
            return list;
        }

        // 核心函数
        largestValuesCore(root, list, 0);

        return list;
    }

    private void largestValuesCore(TreeNode root, List<Integer> retList, int level) {
        if (null == root) {
            return;
        }
        if (retList.size() - 1 < level) {
            retList.add(Integer.MIN_VALUE);
        }
        Integer iItem = retList.get(level);

        if (iItem.intValue() < root.val) {
            retList.set(level, root.val);
        }

        largestValuesCore(root.left, retList, level + 1);
        largestValuesCore(root.right, retList, level + 1);

    }

    /**
    *	测试例子
    */
    public static void main(String[] args) {
        final TreeNode root = new TreeNode(3);

        root.left = new TreeNode(9);
        root.right = new TreeNode(20);

        // root.left.left = new TreeNode(3);
        // root.left.right = new TreeNode(4);

        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        final Solution solution = new Solution();

        final List<Integer> ret = solution.largestValues(root);
        
        System.out.println(ret);
        return;
    }
}

解：

通过递归实现。

① 递归结束条件：碰到叶节点。

② 在进行DFS遍历二叉树的同时，传入参数level给定每次递归的层级，通过层级来进行对当前level的最大值进行比较和替换。

（如果list中没有当前层级的数据，则初始化Integer.MIN_VALUE，有则取出来和当前数值进行比较，若当前值更大则将当前值替换成list中的数值。）

时间复杂度：遍历每个节点，0(N)

空间复杂度：递归需要每向下一层就需要入栈，O(h + h + h) 。三个h分别存储root节点、每层max的值，该层对应的level。