代码随想录之双指针、链表、二叉树、栈与队列

数组

移除元素——双指针法

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素。

使用双指针的思路，定义快慢指针，快指针：寻找新数组的元素，新数组就是不含有目标元素的数组；慢指针：指向更新新数组下标的位置

class Solution {
    public int removeElement(int[] nums, int val) {
        int fast = 0, slow = 0;
        // fast用于检查是否等于val，slow用于计算不等于val的数目
        while(fast != nums.length){
            if(val != nums[fast]){
                nums[slow] = nums[fast];
                slow++;
                fast++;
            } else {
                fast++;
            }
        }
        return slow;
    }
}

类似的双指针法（滑动窗口）——长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int fast = 0, slow = 0;
        // slow指向子数组的头一个元素
        int sum = target;
        int len = nums.length + 1;
        while(fast < nums.length){
            if(nums[fast] < sum){
                sum -= nums[fast];
                fast++;
            } else {
                if(len > fast - slow + 1){
                    len = fast - slow + 1;
                }
                sum += nums[slow];
                slow++;
            }
        }
        return len == nums.length + 1 ? 0 : len;
    }
}

滑动窗口和哈希表结合——水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

class Solution {
    public int totalFruit(int[] fruits) {
        int slow = 0, fast = 0;
        int total = 0;
        int[] count = new int[fruits.length];
        int len = 0;
        while(fast < fruits.length){
            count[fruits[fast]]++;
            if(count[fruits[fast]] == 1){
                total++;
            }
            while(total > 2){
                count[fruits[slow]]--;
                if(count[fruits[slow]] == 0){
                    total--;
                }
                slow++;
            }
            fast++;
            if(len < fast - slow){
                len = fast - slow;
            }
        }
        return len;
    }
}

升级版滑动窗口和哈希表——无重复字符的最长字串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int fast = 0;
        int res = 0;
        for(int slow = 0; slow < s.length(); slow++){
            if(slow != 0){
                set.remove(s.charAt(slow - 1));
            }
            while(fast != s.length() && !set.contains(s.charAt(fast))){
                set.add(s.charAt(fast));
                fast++;
            }
            res = Math.max(res, fast - slow);
        }
        return res;
    }
}

找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

这里利用小写字母特性，只使用26位哈希表（数组），节约空间

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(s.length() < p.length()){
            return res;
        }
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for(int i = 0; i < p.length(); i++){ // 先看前p位
            pCount[p.charAt(i) - 'a']++;
            sCount[s.charAt(i) - 'a']++;
        }

        if(Arrays.equals(sCount, pCount)){
            res.add(0);
        }

        for(int i = p.length(); i < s.length(); i++){ // 看后面的位数
            --sCount[s.charAt(i - p.length()) - 'a']; // 滑动窗口，失去一个得到一个
            ++sCount[s.charAt(i) - 'a'];
            if(Arrays.equals(sCount, pCount)){
                res.add(i - p.length() + 1);
            }
        }

        return res;
    }
}

双指针收缩——盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

使用双指针收缩容器，注意比较left和right来判断收缩哪边

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int max = 0, area;
        while(left < right){
            area = Math.min(height[left], height[right]) * (right - left);
            max = Math.max(max, area);
            if(height[left] < height[right]){
                left++;
            } else {
                right--;
            }
        }
        return max;
    }
}

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

class Solution {
    public int trap(int[] height) {
        // 下标i处的雨水由leftMax和rightMax决定
        int sum = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while(left < right){
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if(height[left] < height[right]){
                sum += leftMax - height[left];
                left++;
            } else {
                sum += rightMax - height[right];
                right--;
            }
        }
        return sum;
    }
}

螺旋矩阵

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

class Solution {
    public int[][] generateMatrix(int n) {
        int l = 0, r = n - 1, t = 0, b = n - 1;
        int[][] res = new int[n][n];
        int k = 1;
        while(true){
            for(int i = l; i <= r; i++) res[t][i] = k++;
            if(++t > b) break;
            for(int i = t; i <= b; i++) res[i][r] = k++;
            if(--r < l) break;
            for(int i = r; i >= l; i--) res[b][i] = k++;
            if(--b < t) break;
            for(int i = b; i >= t; i--) res[i][l] = k++;
            if(++l > r) break;
        }
        return res;
    }
}

链表

链表的基本操作

移除元素

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 哨兵结点，对开始的结点分类讨论
        while(head != null && head.val == val){
            head = head.next;
        }
        ListNode cur = head;
        while(cur != null && cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}

反转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode temp, prev = null;
        while(cur != null){
            temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}

两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

使用递归算法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return head;
        // 递归
        ListNode next = head.next;
        ListNode newNode = swapPairs(head.next.next);
        next.next = head;
        head.next = newNode;
        return next;
    }
}

删除链表的倒数第N个节点

使用双指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dum = new ListNode(0, head);
        ListNode fast = head, slow = dum;
        for(int i = 0; i < n; i++){
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dum.next;
    }
}

链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

先遍历一遍得到长度，再对齐两个链表的指针，最后一起移动检查节点是否相等

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0, lenB = 0;
        ListNode curA = headA, curB = headB;
        while(curA != null){
            curA = curA.next;
            lenA++;
        }
        while(curB != null){
            curB = curB.next;
            lenB++;
        }

        curA = headA; curB = headB;
        if(lenA > lenB){
            for(int i = 0; i < lenA - lenB; i++){
                curA = curA.next;
            }
        } else {
            for(int i = 0; i < lenB - lenA; i++){
                curB = curB.next;
            }
        }

        while(curA != null){
            if(curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}

环形链表

题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。

一个数学问题，双指针先双倍移动以判断环，再单倍移动以得到起始位置

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                slow = head;
                while(fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}

哈希表

字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

使用HashMap，键为排序后的str，值为str数组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for(String str : strs){
            char[] s = str.toCharArray();
            Arrays.sort(s);
            // 如果 Map 中没有键 new String(s)，则创建一个新的 ArrayList 并将其与键关联
            map.computeIfAbsent(new String(s), k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(map.values());
    }
}

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。

使用HashMap记录差值和索引的键值对

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[2];
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i])){
                res[0] = map.get(nums[i]);
                res[1] = i;
                return res;
            }
            map.put(target - nums[i], i);
        }
        return res;
    }
}

四数相加

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

类似于两数之和，将nums1和nums2视为一组，nums3和nums4视为一组

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        // nums1和nums2一组，nums3和nums4一组
        for(int i : nums1){
            for(int j : nums2){
                map.put(i + j, map.getOrDefault(i + j, 0) + 1);
            }
        }

        for(int i : nums3){
            for(int j : nums4){
                if(map.containsKey(0 - i - j)){
                    res += map.get(0 - i - j);
                }
            }
        }

        return res;
    }
}

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

使用双指针法更简单，先进行排序，再遍历数组，并使用left和right指向剩下的两个数字，注意题干中的去重
对于四数之和，直接两层循环，剩下两个数就可以用双指针了

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        // 先排序，以使用双指针
        Arrays.sort(nums);

        int left, right, sum;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0){
                return res;
            }

            // 去除重复三元组
            if(i > 0 && nums[i - 1] == nums[i]){
                continue;
            }

            left = i + 1;
            right = nums.length - 1;
            while(left < right){
                sum = nums[i] + nums[left] + nums[right];
                if(sum > 0){
                    right--;
                } else if(sum < 0){
                    left++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重
                    while(left < right && nums[left] == nums[left + 1]){
                        left++;
                    }
                    while(left < right && nums[right] == nums[right - 1]){
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }

        return res;
    }
}

字符串

翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: “the sky is blue”
输出: “blue is sky the”
示例 2：
输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

借助StringBuilder移除多余空格，将整个字符串反转，将每个单词反转

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = removeSpace(s);
        reverseString(sb, 0, sb.length() - 1);
        reverseEachWord(sb);
        return sb.toString();
    }
    
    private StringBuilder removeSpace(String s){
        int start = 0;
        int end = s.length() - 1;
        while(s.charAt(start) == ' ') start++;
        while(s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while(start <= end){
            char c = s.charAt(start);
            if(c != ' ' || sb.charAt(sb.length() - 1) != ' '){ // 去除单词间的多余空格
                sb.append(c);
            }
            start++;
        }
        return sb;
    }

    private void reverseString(StringBuilder sb, int start, int end){
        while(start < end){ // 头尾交换
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }

    private void reverseEachWord(StringBuilder sb){
        int start = 0;
        int end = 1; // 双指针找到单词
        int n = sb.length();
        while(start < n){
            while(end < n && sb.charAt(end) != ' '){
                end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }
}

KMP算法——实现strStr()

实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

使用KMP算法，先根据回文计算next数组，再双指针，needle指针用于回溯

class Solution {
    public int strStr(String haystack, String needle) {
        int[] next = next(needle);
        // 双指针分别指向两个字符串的匹配位，needle用于回溯，handle始终保持前移
        int i = 0, j = 0;
        int m = haystack.length(), n = needle.length();
        while((m - i) >= (n - j)){
            if(haystack.charAt(i) == needle.charAt(j)){
                i++; j++;
            } else if (j != 0){
                j = next[j - 1];
            } else {
                i++;
            }
            if(j == n) {
                return i - j;
            }
        }
        return -1;
    }

    static int[] next(String needle){
        int[] next = new int[needle.length()];
        int i = 0, j = 1;

        while(j != needle.length()){
            if(needle.charAt(i) == needle.charAt(j)){
                i++;
                next[j] = i; // 回文有多少字符，而数组从0开始
                j++;
            } else if(i != 0){
                // 回溯到已检查字符串的回文的下一位，进行检查匹配
                i = next[i - 1];
            } else { // 无法回溯，为默认值0
                j++;
            }
        }

        return next;
    }
}

栈与队列

用队列表示栈

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    
    public void push(int x) {
        // 放在辅助队列使新加元素位于头部
        q2.offer(x);
        while(!q1.isEmpty()){
            q2.offer(q1.poll());
        }
        // 交换两队列的满空状态
        Queue<Integer> queueTemp;
        queueTemp = q1;
        q1 = q2;
        q2 = queueTemp;
    }
    
    public int pop() {
        return q1.poll();
    }
    
    public int top() {
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

栈的应用——有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

使用栈匹配

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(char c : s.toCharArray()){
            if(c == ')' && !stack.isEmpty() && stack.peek() == '('){
                stack.pop();
            } else if(c == ']' && !stack.isEmpty() && stack.peek() == '['){
                stack.pop();
            } else if(c == '}' && !stack.isEmpty() && stack.peek() == '{'){
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

队列的应用——滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。

实现一个单调递减的队列来peek最大值

class MyQueue { // 该队列应当保证单调递减
    Deque<Integer> queue = new LinkedList<>();

    void poll(int val){ // 只弹出最大值，其余值会自动消亡
        if(!queue.isEmpty() && val == queue.peek()){
            queue.poll();
        }
    }

    void add(int val){
        while(!queue.isEmpty() && val > queue.getLast()){
            queue.removeLast(); // 抹除更小值保证单调递减
        }
        queue.add(val);
    }

    int peek(){
        return queue.peek();
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 1){
            return nums;
        }
        int len = nums.length - k + 1;
        int res[] = new int[len];
        int num = 0;
        MyQueue queue = new MyQueue();
        // 此时队列只有最大值及其后面的次大值，以此类推
        for(int i = 0; i < k; i++){
            queue.add(nums[i]);
        }
        res[num++] = queue.peek();

        for(int i = k; i < nums.length; i++){
            queue.poll(nums[i - k]);
            queue.add(nums[i]);
            res[num++] = queue.peek();
        }

        return res;
    }
}

优先级队列——前K个高级元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

先用HashMap记录键值对，再用优先级队列排序

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num : nums){
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        // 一个大顶堆
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            pq.add(new int[]{entry.getKey(), entry.getValue()});
        }

        int[] ans = new int[k];
        for(int i = 0; i < k; i++){
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}

二叉树

二叉树的基本操作

二叉树的非递归遍历

以后序遍历为例，使用栈来辅助

/**
 * 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> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            res.add(cur.val);
            if(cur.left != null){
                stack.push(cur.left);
            }
            if(cur.right != null){
                stack.push(cur.right);
            }
        }
        Collections.reverse(res);
        return res;
    }
}

二叉树的层序遍历

递归或借助队列实现

/**
 * 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>> res = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        // bfs(root);
        recursive(root, 0);
        return res;
    }

    // 递归
    private void recursive(TreeNode root, int depth){
        if(root == null) return;
        depth++;

        if(res.size() < depth){
            List<Integer> item = new ArrayList<>();
            res.add(item);
        }
        res.get(depth - 1).add(root.val);
        
        recursive(root.left, depth);
        recursive(root.right, depth);
    }

    // 借助队列
    private void bfs(TreeNode root){
        if(root == null) return;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        while(!queue.isEmpty()){
            List<Integer> item = new ArrayList<Integer>();
            int len = queue.size();

            while(len > 0){
                TreeNode temp = queue.poll();
                item.add(temp.val);

                if(temp.left != null){
                    queue.offer(temp.left);
                }
                if(temp.right != null){
                    queue.offer(temp.right);
                }

                len--;
            }

            res.add(item);
        }
    }
}

翻转二叉树

递归交换左右孩子即可

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

    private void swapChildren(TreeNode root){
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。

递归时同时带上path用于记录到达当前节点的路径

/**
 * 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<String> res = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        // recursive(root, "");
        byStack(root);
        return res;
    }

    // 递归法
    private void recursive(TreeNode root, String path){ // path表示到达该节点的路径
        if(root == null) return;
        if(root.left == null && root.right == null){ // 叶子节点
            res.add(new StringBuilder(path).append(root.val).toString());
            return;
        }
        String newPath = new StringBuilder(path).append(root.val).append("->").toString();
        recursive(root.left, newPath);
        recursive(root.right, newPath);
    }

    // 迭代法
    private void byStack(TreeNode root){
        if(root == null) return;
        Stack<Object> stack = new Stack<>();
        // 节点和路径同时入栈
        stack.push(root);
        stack.push(root.val + "");
        while(!stack.isEmpty()){
            String path = (String) stack.pop();
            TreeNode cur = (TreeNode) stack.pop();
            if(cur.left == null && cur.right == null){
                // 叶子节点
                res.add(path);
            }
            if(cur.left != null){
                stack.push(cur.left);
                stack.push(path + "->" + cur.left.val);
            }
            if(cur.right != null){
                stack.push(cur.right);
                stack.push(path + "->" + cur.right.val);
            }
        }
    }
}

从中序遍历与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

root在后序遍历最后一个节点，以此切割中序序列（用map记录键值对来查找），再根据左右子树的长度切割后序序列

/**
 * 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 {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return findNode(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    // 表示下标范围
    private TreeNode findNode(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight){
        if(inLeft > inRight || postLeft > postRight) return null;
        // 找到后序遍历最后一个元素在中序遍历位置
        int rootIndex = map.get(postorder[postRight]);
        TreeNode root = new TreeNode(inorder[rootIndex]);
        // 在中序遍历和后序遍历中，左子树是等长的
        // 使用root下表切割中序序列
        root.left = findNode(inorder, inLeft, rootIndex - 1, postorder, postLeft, postLeft + rootIndex - 1 - inLeft);
        root.right = findNode(inorder, rootIndex + 1, inRight, postorder, postLeft + rootIndex - inLeft, postRight - 1);
        return root;
    }
}

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 使用后序遍历实现自底向上
        // 只返回p,q或者null,或者二者的公共祖先
        if(root == p || root == q || root == null) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 左右分别有p,q,说明为公共祖先，返回自己
        if(left != null && right != null) return root;
        // 只有左边不为null,说明要么p,q没有都找到，要么left为公共祖先，返回left
        if(left != null && right == null) return left;
        if(left == null && right != null) return right;
        //p,q都没找到，返回null
        return null;
    }
}

二叉搜索树

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

/**
 * 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 {
    TreeNode pre = null; // 记录中序遍历的前一个节点，从而得到左子树的最大值
    public boolean isValidBST(TreeNode root) {
        // 中序遍历
        if(root == null) return true;
        boolean left = isValidBST(root.left);
        if(pre != null && pre.val >= root.val) return false;
        pre = root;
        return left && isValidBST(root.right);
    }
}

二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

/**
 * 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 {
    TreeNode parent = new TreeNode(0);
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) root = new TreeNode(val);
        recursive(root, val);
        return root;
    }

    private void recursive(TreeNode root, int val){
        if(root == null){
            // 落到底部，可以插入
            TreeNode cur = new TreeNode(val);
            if(val < parent.val) parent.left = cur;
            else parent.right = cur;
            return;
        }
        parent = root;
        if(val < root.val) recursive(root.left, val);
        if(val > root.val) recursive(root.right, val);
        return;
    }
}

删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

分情况讨论

/**
 * 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 deleteNode(TreeNode root, int key) {
        // 1.没找到节点，返回null
        if(root == null) return root;
        
        if(root.val == key){
            // 2.左右子树都为空，直接删除
            if(root.left == null && root.right == null){
                return null;
            }
            // 3.左子树为空，将右子树拉上来拼接
            if(root.left == null){
                return root.right;
            }
            // 4.右子树为空，类似
            if(root.right == null){
                return root.left;
            }
            // 5.左右子树都不为空，将左子树拼接到右子树最左边节点的左孩子上
            TreeNode cur = root.right;
            while(cur.left != null){
                cur = cur.left;
            }
            cur.left = root.left;
            root = root.right;
            return root;
        }
        // 拼接与回溯
        if(key < root.val) root.left = deleteNode(root.left, key);
        if(key > root.val) root.right = deleteNode(root.right, key);
        return root;
    }
}