数组

704. 二分查找(easy)

描述

排序数组、无重复

要点分析

主要是在开闭区间选择上决定处理边界的不同， [left,right],还是[left，right)
闭区间定义left，right = num.size-1,这样[left,right]两边都能取值，while循环比较时也是闭环
开区间定义left，right = num.siz, 这样[left,right) 单边取值即可，while循环比较时开环

核心代码

//闭区间
定义left , right = nums.size-1  //由于两边都能取到 因此是闭区间
while(left<=right){
    mid = (right+left) /2
    if(nums[mid] == target){
        return mid
    } else if( nums[mid] < target){
        //右边区间 [mid+1,right]
        left = mid + 1
    } else {
        //左边区间 [left,mid-1]
        right = mid - 1
    }
}


//开区间
定义left , right = nums.size  //由于两边都能取到 因此是闭区间

while(left<right){
    mid = (right+left) /2
    if(nums[mid] == target){
        return mid
    } else if( nums[mid] < target){
        //右边区间 [mid+1,right）
        left = mid +1
    } else {
        //左边区间 [left,mid)
        right = mid
    }
}

27. 移除数组元素(easy)

描述

一般会要求 O(1)空间，即不开辟新空间，返回移除元素后数组的长度

核心要点

有2种解法

暴力法，发现需要移除的元素，整体往前移动一位

这里就涉及到 双重for循环+元素交换，还需要改变size长度，

快慢指针法

通过双指针简化for循环，这里涉及到快慢指针的定义
快指针：不含有目标元素 (扫描)
慢指针：指向更新数组下标的位置 (不是目标值前进，是目标值停止)

核心代码

 //双指针法
fun removeElement(nums: IntArray, `val`: Int): Int {
    if (nums.isEmpty()) return -1
    var slow = 0
    for (fast in nums.indices) {
        if (nums[fast] != `val`) {
            nums[slow] = nums[fast]
            slow++
        }
    }

    //[0-slow]即为符合预期的数组元素
    return slow
}

//双重for循环暴力破解
//发现相等的直接往前移动填满
fun removeElement2(nums: IntArray, `val`: Int): Int {
    var size = nums.size
    var index = 0
    while (index < size) {
        if (nums[index] == `val`) {
            //暴力填充数组
            for (indexInner in index until nums.size) {
                nums[indexInner - 1] = nums[indexInner]
            }
            //此时下标i以后的数值向前移动了一位，所以i也向前移动一位
            index--
            //此时数组的大小-1
            size--
        }
        index++
    }
    return index
}

977.有序数组的平方(easy)

描述

有序数组，平方之后也按顺序排序，不开辟新的空间

核心要点

平方之后，最大值分部在两头，这样就可以使用快慢指针来交换排序

代码

fun sortedSquares(nums: IntArray): IntArray {

    var left = 0
    var right = nums.size - 1
    var result = IntArray(nums.size)
    var index = nums.size - 1

    while (left <= right) {
        if (nums[left] * nums[left] > nums[right] * nums[right]) {
            result[index--] = nums[left] * nums[left]
            left++
        } else {
            result[index--] = nums[right] * nums[right]
            right--
        }
    }
    return result
}

209.(滑动窗口)长度最小的子数组(mid)

描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0，如:
输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

要点分析

暴力循环双重for循环
滑动窗口法

滑动窗口其实也是双指针的一种，需要重点把握的是
窗口内是什么？
窗口起始位置如何移动？
窗口结束位置如何移动？
搞清楚这三个问题基本上就能拿下滑动窗口
滑动窗口有着自己的套路

回归到本题中，窗口内就是满足 sum>=s长度最小的连续子数组
窗口的起始位置如何移动：当前窗口值大于s了，窗口就要向前移动了(缩小窗口)
窗口的结束位置如何移动：窗口结束位置就是遍历数组的指针即for循环中的索引
本题的关键是如何调节起始窗口的位置

可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置，从而将O(n^2)降低为O(n)
代码

//暴力法
fun minSubArrayLen0(target: Int, nums: IntArray): Int {
    var sum = 0
    //子序列长度
    var subLength = 0
    //每次比较之后的最终长度
    var result = Int.MAX_VALUE
    for (i in nums.indices) {
        //每次sum = 0 重新累加
        sum = 0
        for (j in i until nums.size) {
            sum += nums[j]
            if (sum >= target) {
                //记录此时的长度
                subLength = j - i + 1
                //对比之前的长度
                result = if (result < subLength) return result else subLength
                //符合条件跳出循环
                break
            }
        }
    }
    return if(result == Int.MAX_VALUE) 0 else result
}

//滑动窗口
fun minSubArrayLen(target: Int, nums: IntArray): Int {
    var sum = 0
    var subLength = 0
    var result = Int.MAX_VALUE

    //滑动窗口起始位置
    var left = 0

    for(right in nums.indices){
        //开始累加
        sum += nums[right]
        //滑动窗口
        while(sum >= target){
            subLength = right - left +1
            result = if(result < subLength) result else subLength
            //移动窗口左边界
            sum-=nums[left++]
        }
    }
    return if(result == Int.MAX_VALUE) 0 else result
}

关于滑动窗口 B站也有讲解视频 https://www.bilibili.com/video/BV1V44y1s7zJ?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=f9b305274daffa5db46d0a6df9e6bdfa

字符串

344. 反转字符串(easy)

核心要点

双指针
注意边界while(left<right)

通常这个方法作为一个辅助函数使用

代码

//典型的双指针
fun reverseString(s: CharArray): Unit {
    if(s.isEmpty()) return
    var left = 0
    var right = s.size - 1
    while(left < right){
        //交换
        var temp = s[left]
        s[left] = s[right]
        s[right] = temp

        left++
        right--
    }
}

541. 反转字符串II

描述

给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = “abcdefg”, k = 2
输出: “bacdfeg”

要点分析

只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。

代码

fun reverseStr(s: String, k: Int): String {
    val chars = s.toCharArray()
    var index = 0
    while (index < chars.size) {
        var left = index
        //这里是判断尾数够不够k个来取决end指针的位置
        var right = Math.min(chars.size - 1, left + k - 1)
        while (left < right) {
            val temp = chars[left]
            chars[left] = chars[right]
            chars[right] = temp
            //移动
            left++
            right--
        }
        index += 2 * k
    }
    return chars.toString()
}

剑指offer05 替换空格

描述

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
示例 1：输入：s = “We are happy.”
输出：”We%20are%20happy.”

要点分析：

不开辟新的空间，统计空格，扩充数组空间
双指针技巧

代码

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0; // 统计空格的个数
        int sOldSize = s.size();
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                count++;
            }
        }
        // 扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小
        s.resize(s.size() + count * 2);
        int sNewSize = s.size();
        // 从后先前将空格替换为"%20"
        for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
            if (s[j] != ' ') {
                s[i] = s[j];
            } else {
                s[i] = '0';
                s[i - 1] = '2';
                s[i - 2] = '%';
                i -= 2;
            }
        }
        return s;
    }
}

哈希表

需要使用键值对的情形，在处理字符串的时候可以提供一种特别的思路，

将字符做好映射

 // 26个字母
val records = IntArray(26)

for(element in s){
    records[element -'a']++
}

字母比较

可以通过字母数据，char-‘a’ 转换到字母位置，通常配合list更好处理

使用set 元素唯一性的特点
1. 两数之和(easy)

描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

要点分析

转换成键值对可以减少for循环

代码

fun twoSum(nums: IntArray, target: Int): IntArray {
    if(nums.isEmpty()) return intArrayOf()
    var tempMap = mutableMapOf<Int,Int>()
    var records = mutableListOf<Int>()
    for(index in nums.indices){
        tempMap[nums[index]] = index
        val matcher = target-nums[index]
        if(tempMap.containsKey(matcher)){
            records.add(tempMap[nums[index]] ?:0)
            records.add(index)
            return records.toIntArray()
        }
    }
    return IntArray(0)
}

242.有效的字母异位数(easy)

描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true
示例 2: 输入: s = “rat”, t = “car” 输出: false
说明: 你可以假设字符串只包含小写字母。

要点分析

利用26个字母有限数目，哈希成字母表

代码

 fun isAnagram(s: String, t: String): Boolean {
    if(s.length != t.length) return false
    // 26个字母
    val records = IntArray(26)

    for(element in s){
        records[element -'a']++
    }

    for(element in t){
        records[element-'a']--
    }

    //如果有效字母异位词此时record数组应该都为0
    for(value in records) {
        //说明有不匹配的
        if(value != 0){
            return false
        }
    }
    return true
}

349. 两个数组的交集(easy)

描述

给定两个数组，编写一个函数来计算他们的交集
示例:
输入: nums1=[1,2,2,1], nums2=[2,2]
输出: [2]

要点分析

将数组转化成不重复 hashset
比较两个具有唯一值的 hashset

代码

fun intersection(nums1: IntArray, nums2: IntArray): IntArray {
    //边界判断
    if(nums1.isEmpty() || nums2.isEmpty()) return IntArray(0)
    val result = mutableListOf<Int>()
    //将第一个转换为set过滤重复元素
    val numSet = nums1.toSet()
    for(num in nums2){
        if(numSet.contains(num)&&!result.contains(num)){
            result.add(num)
        }
    }
    return result.toIntArray()
}

383. 赎金信

描述

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

要点分析

本题跟 242有效字母异位数比较像，只不过242题相当于 a,b两个字符串是否互相组成，而本题是求字符串a能否由字符串b组成

代码

//字母匹配
fun canConstruct(ransomNote: String, magazine: String): Boolean {
    if(ransomNote.isEmpty() || magazine.isEmpty()) return false
    //26个字符
    var records = IntArray(26)

    //用magazine 添加
    for(charMagazine in magazine){
        records[charMagazine-'a']+=1
    }
    //用信封消除
    for(charRansomeNote in ransomNote){
        records[charRansomeNote-'a']-=1
    }

    //如果数组中存在负数则表示不匹配的
    for(record in records){
        if(record < 0) return false
    }

    return true
    
}

链表

链表涉及到指针，常用解决方法时双指针、增加虚拟头结点

由于链表的特点是操作当前节点需要找到前一个节点，由于头节点并没有前一个节点因此需要特殊操作，使用虚拟头结点就可以解决这个问题

203 移除链表元素(easy)

描述

删除链表中等于给定值 val 的所有节点
输入：head = [1,4,2,4], val = 4
输出：[1,2]

要点分析

主要是操作链表节点，防止移除元素是头结点，因此需要增加虚拟头节点

代码

// 虚拟节点
fun removeElements(head: ListNode?, `val`: Int): ListNode? {
    if(head == null) return head
    //前置一个虚拟节点
    var virtualHead = ListNode(-1,head)
    var temp:ListNode? = virtualHead
    while(temp?.next != null){
        if(temp.data == `val`){
            //删除
            temp.next = temp?.next?.next
        } else {
            //移动链表指针
            temp = temp.next
        }
    }
    return virtualHead.next
}

206.反转单链表(easy)

核心分析

虚拟头结点
cur节点、pre节点交换
cur，pre 前进

代码

//非递归
fun reverseList(head: ListNode?): ListNode? {
    var pre:ListNode? = null
    var cur = head
    var temp:ListNode? = null
    while(cur !=null){
        //保存 cur的下一个节点,因为接下来要改变cur-next
        temp = cur.next
        //翻转
        cur.next = pre
        //移动 pre和cur
        pre = cur
        cur = temp

    }
    return pre
}

//递归版本
fun reverseList1(head: ListNode?): ListNode? {
    return reverse(null, head)
}

private fun reverse(prev: ListNode?, cur: ListNode?): ListNode? {
    if (cur == null) {
        return prev
    }
    var temp: ListNode? = null
    temp = cur.next // 先保存下一个节点
    cur.next = prev // 反转
    // 更新prev、cur位置
    // prev = cur;
    // cur = temp;
    return reverse(cur, temp)
}

24. 两两交换链表中的元素(mid)

核心要点
跟反转单链表中核心原理一致

保存节点
反转节点
移动节点

fun swapPairs(head: ListNode?): ListNode? {
    if (head == null) return null
    // 构造虚拟节点
    val virtualNode = ListNode(0, head)
    //当前节点
    var cur = virtualNode
    while (cur.next != null && cur.next?.next != null) {
        //保存节点
        val temp = cur.next
        val temp1 = cur.next?.next?.next

        //翻转
        cur.next = cur.next?.next
        cur.next?.next = temp
        cur.next?.next?.next = temp1

        //移动2位 进行下一次循环
        cur = cur.next?.next!!
    }
    return virtualNode.next
}

19. 删除链表倒数第N个节点(easy)

描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：使用一趟扫描实现

核心分析

虚拟头结点
双指针

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了

代码

fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        if(head == null) return null
        //虚拟头节点,这样可以方便处理删除实际头结点的逻辑
        var virtualNode = ListNode(0,head)
        //双指针
        var slowNode = virtualNode
        var fastNode = virtualNode
        //fast 先走n+1步
        while(n > 0){
            fastNode = fastNode.next
            n--;
        }
        //找到倒数第N的节点
        while(fastNode != null){
            slowNode = slowNode.next
            fastNode = fastNode.next
        }
        //此时curNode是倒数n个前节点
        slowNode.next = slowNode.next?.next
        return virtualNode.next
    }

142.环形链表(mid)

核心要点

判断有没有环

经典的快慢指针问题，慢指针每次走1步，快指针每次走2步，那么有可能在环中相交

环的位置

先上结论

从头结点发出一个指针，从相遇节点也发出一个指针
这两个指针每次只走1步，那么这两个指针相遇的时候就是环形入口的节点

那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，（y+z）为一圈内节点的个数A

核心代码

class Solution {
    fun detectCycle(head: ListNode?): ListNode? {
        if(head == null) return null
        var slow = head
        var fast = head
        var hasCircle = false
        //判断是否有环
        while(fast?.next != null){
            //fast 每次走2步,slow每次走1步
            fast = fast.next?.next
            slow = slow?.next
            if(fast == slow){
                hasCircle = true
                break
            }
        }
        //没有环 直接退出
        if(!hasCircle) return null
        //有环 slow回到节点，slow fast每次走1步，相遇则是环的位置
        slow = head
        while(slow != fast){
            slow = slow?.next
            fast = fast?.next
        }
        return slow
        
    }
}

二叉树

二叉树主要考察树的

二叉树的类型

满二叉树: 如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

完全二叉树: 除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

遍历

1.BFS(广度优先遍历)
一层层的遍历，结合队列
2.DFS(深度优先遍历)
先往深走，遇到叶子节点再往回走，递归或者结合栈

前序遍历 中左右
中序遍历左中右
后序遍历左右中

dfs和bfs往往需要配合栈和队列这些数据结构来，在非迭代遍历前中后序

144. (DFS)二叉树前中后遍历(easy)

要点分析

主要分为递归和非递归版本,

递归版本，主要注意递归退出条件，属于深度遍历
非递归版本则是需要借助栈来帮助实现，不过有点注意的是，进栈顺序得保持右左，这样出栈才能恢复成左右

代码

//前序遍历递归法
fun preorderTraversal(root: TreeNode?): List<Int> {
    val list = mutableListOf<Int>()
    preOrder(root, list)
    return list
}

private fun preOrder(root: TreeNode?, list: MutableList<Int>) {
    if (root == null) return
    //根
    list.add(root.`val`)
    //左
    preOrder(root.left,list)
    //右
    preOrder(root.right,list)
}

//前序遍历迭代法 DFS
fun preorderTraversal2(root: TreeNode?): List<Int> {
    val list = mutableListOf<Int>()
    val stack = Stack<TreeNode>()
    if(root == null) return list
    stack.push(root)
    while(!stack.isEmpty()){
        //获取节点
        val node = stack.pop()
        list.add(node.`val`)
        //子节点压栈 栈先右后左
        if(node.right!=null) stack.push(node.right)
        if(node.left!=null) stack.push(node.left)
    }
    return list


}

145. 二叉树后序遍历

要点分析

后序遍历是左右中，在递归法中比较好操作，交换一下顺序即可，

非递归 **后序 **可以按照中右左，然后再对数组翻转

代码

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
            if (node->right) st.push(node->right); // 空节点不入栈
        }
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
        return result;
    }
};

146. 二叉树中序遍历

要点分析

非递归代码比较难搞，需要结合栈来处理
代码

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

102.(BFS)二叉树层序遍历(mid）

要点分析

层序遍历二叉树就是从左到右一层层的遍历二叉树，这里需要借助 队列来实现，队列先进先出，符合一层层遍历的逻辑(栈的话先进后出适合模拟深度优先遍历)，层序遍历是典型的广度优先遍历
需要队列记录每一层的数据

代码

fun levelOrder(root: TreeNode?): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    if (root == null) return result
    val queue = LinkedList<TreeNode>()
    queue.push(root)
    //while循环控制从上到下
    while (!queue.isEmpty()) {
        val size = queue.size
        //记录这一层的节点值
        val curList = LinkedList<Int>()
        for (i in 0..size) {
            val curNode = queue.pop()
            curList.add(curNode.`val`)
            if (curNode.left != null) queue.push(curNode.left)
            if (curNode.right != null) queue.push(curNode.right)
        }
        result.add(curList)
    }
    return result
}

226. 翻转二叉树(easy)

要点分析

把每个节点的左右孩子交换一下即可

递归 (最简单操作)

着重3个核心点

确定递归函数的参数和返回值

1	fun invertTree(root: TreeNode?): TreeNode?

确定终止条件
1
if(root == null) return null

确定单层递归的逻辑

1
2
3

invertTree(root.left)
invertTree(root.right)
swap(root)

广度优先 (层序遍历)
深度优先遍历(非递归迭代)

代码

递归

//递归法
fun invertTree(root: TreeNode?): TreeNode? {
    if(root == null) return null
    swap(root)
    invertTree(root.left)
    invertTree(root.right)
    return root
}
//交换节点数值
private fun swap(node: TreeNode){
    val temp = node.left
    node.left = node.right
    node.right = temp
}

层次遍历 (广度优先）

//层次遍历 广度优先遍历
fun invertTree2(root: TreeNode?): TreeNode? {
    val queue = LinkedList<TreeNode>()
    if(root == null) return root
    queue.add(root)
    while(!queue.isEmpty()){
        val size =  queue.size
        for(i in 0..size){
            val curNode = queue.pop()
            //翻转
            swap(curNode)
            //遍历
            if(curNode.left != null) queue.push(curNode.left)
            if(curNode.right != null) queue.push(curNode.right)
        }
    }
    return root
}

101. 对称二叉树(easy)

要点分析

比较的是根节点个左右子树是不是互相翻转的，即两个子树里侧和外侧的元素是否相等，

递归法

首先是三部曲

确定递归函数的参数和返回值
确定终止条件
确定单层递归的逻辑

迭代法

这里使用队列

代码

递归法

fun isSymmetric(root: TreeNode?): Boolean {
        if(root == null) return true
        return compare(root.left,root.right)
    }

fun compare(left:TreeNode?,right TreeNode?):Boolean {
    //处理空节点情况
    // if(left == null && right == null) return true
    // else if(left == null && right != null) return false
    // else if(left !=null && right == null) return false
    // else if(left.`val` != right.`val`) return false

    if(left == null || right == null) return left == right
    if(left.`val` != right.`val`) return false

    var outer = compare(left.left,right.right)
    var inner = compare(left.right,right.left)
    return outer && inner
}

迭代法

使用栈

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        stack<TreeNode*> st; // 这里改成了栈
        st.push(root->left);
        st.push(root->right);
        while (!st.empty()) {
            TreeNode* leftNode = st.top(); st.pop();
            TreeNode* rightNode = st.top(); st.pop();
            if (!leftNode && !rightNode) {
                continue;
            }
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            st.push(leftNode->left);
            st.push(rightNode->right);
            st.push(leftNode->right);
            st.push(rightNode->left);
        }
        return true;
    }
};

使用队列

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root->left);   // 将左子树头结点加入队列
        que.push(root->right);  // 将右子树头结点加入队列
        
        while (!que.empty()) {  // 接下来就要判断这两个树是否相互翻转
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  // 左节点为空、右节点为空，此时说明是对称的
                continue;
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);   // 加入左节点左孩子
            que.push(rightNode->right); // 加入右节点右孩子
            que.push(leftNode->right);  // 加入左节点右孩子
            que.push(rightNode->left);  // 加入右节点左孩子
        }
        return true;
    }
};

104. 二叉树的最大深度(easy)

要点分析

给定一个二叉树，找到最大深度，二叉树的深度为根节点到最远叶子节点的最长路径上的节点数，使用前序和后序遍历都是OK的。
使用前序(中左右)得到的是深度
使用后序(左右中)得到的是高度

递归

三板斧

确定递归函数的参数和返回值：参数是根节点返回值就是这个树的深度
1
fun maxDepth(root: TreeNode?): Int
确定终止条件
1
if(root == null) return 0
单层递归的逻辑

先求左子树深度，再求右子树的深度，最后取左右深度最大的数值，再+1(顶点节点)

val leftdepth = getDepth(root.left)
val rightdepth = getDepth(root.right)
val depth = 1 + Math.max(leftdepth,rightdepth)
return depth

广度优先遍历

按层遍历，每层+1即可
代码

递归

fun maxDepth(root: TreeNode?): Int {
    if(root == null) return 0
    return getDepth(root)
}
private fun getDepth(root:TreeNode?):Int{
    if(root == null) return 0
    val leftdepth = getDepth(root.left)
    val rightdepth = getDepth(root.right)
    val depth = 1 + Math.max(leftdepth,rightdepth)
    return depth
}

广度优先遍历

//迭代 广度优先遍历
fun maxDepth1(root: TreeNode?): Int {
    if(root == null) return 0
    var depth = 0
    val queue = LinkedList<TreeNode>()
    queue.push(root)
    while(!queue.isEmpty()){
        val size = queue.size
        depth++
        for(i in 0..size-1){
            val curNode = queue.pop()
            if(curNode.left != null) queue.push(curNode.left)
            if(curNode.right != null) queue.push(curNode.right)
        }
    }
    return depth
}

111. 二叉树的最小深度(easy)

要点分析

跟二叉树最大深度看似相同

递归

递归三部曲

确定函数输出参数和返回值
1
fun getMinDepth(node: TreeNode?): Int
确定终止条件
1
if (node == null) return 0

确定单层递归逻辑

//判断真正的最小深度
if (node.left == null && node.right != null) return 1 + leftDepth
if (node.left != null && node.right == null) return 1 + rightDepth

var result = 1 + Math.min(leftDepth, rightDepth)
return result

迭代

BSF，不过终止条件是左右节点都为空说明找到了最小深度

代码

递归

//递归法
fun minDepth(root: TreeNode?): Int {
    if (root == null) return 0
    return getMinDepth(root)
}

fun getMinDepth(node: TreeNode?): Int {
    if (node == null) return 0
    val leftDepth = getMinDepth(node.left)
    val rightDepth = getMinDepth(node.right)
    //判断真正的最小深度
    if (node.left == null && node.right != null) return 1 + leftDepth
    if (node.left != null && node.right == null) return 1 + rightDepth

    var result = 1 + Math.min(leftDepth, rightDepth)
    return result
}

BFS

//迭代法 跟最大深度类似，但是最大深度是一直到底，而这里只需要找到左右孩子为空即可
fun minDepth1(root: TreeNode?): Int {
    if (root == null) return 0
    var depth = 0
    val queue = LinkedList<TreeNode>()
    queue.push(root)
    while (!queue.isEmpty()) {
        val size = queue.size
        depth++
        for (i in 0..size - 1) {
            val curNode = queue.pop()
            if (curNode.left != null) queue.push(curNode.left)
            if (curNode.right != null) queue.push(curNode.right)
            //左右子节点都为空则找到最小深度
            if (curNode.right == null && curNode.left == null) return depth
        }
    }
    return depth
}

257.二叉树的所有路径(mid)

描述

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

要点分析

涉及到回溯算法
回溯跟递归是一家，因此又要来到了熟悉的递归三板斧

函数入参及返回值

1	fun pathTraversal(node: TreeNode?, path: StringBuilder)

递归终止条件

找到了子节点，即cur不为空，且左右孩子都为空的时候就找到叶子节点了

单层递归逻辑

if (null != node) {
    val newPath = StringBuilder(path)
    // 选择路径
    newPath.appendChar(node.`val`)
    if (null == node.left && null == node.right) {
        // 到达叶子节点
        result.add(newPath.toString())
    } else {
        // 路径中途，递归左右子树
        pathTraversal(node.left, newPath)
        pathTraversal(node.right, newPath)
    }
}

代码

fun binaryTreePaths(root: TreeNode?): List<String> {

    val result = LinkedList<String>()

    fun pathTraversal(node: TreeNode?, path: StringBuilder) {
        if (null != node) {
            val newPath = StringBuilder(path)
            // 选择路径
            newPath.appendChar(node.`val`)
            if (null == node.left && null == node.right) {
                // 到达叶子节点
                result.add(newPath.toString())
            } else {
                // 路径中途，递归左右子树
                pathTraversal(node.left, newPath)
                pathTraversal(node.right, newPath)
            }
        }
    }

    pathTraversal(root, StringBuilder())

    return result
}

private fun StringBuilder.appendChar(num: Int) {
    if (length == 0) {
        append("$num")
    } else {
        append("->$num")
    }
}

404.左叶子之和(easy)

要点分析
左叶子：如果左节点不为空，且左节点没有左右孩子，那么这个节点的左节点就是左叶子。
因此当前节点是无法判断的需要通过节点的父节点来判断其左孩子是不是左叶子

代码

 //递归法
fun sumOfLeftLeaves(root: TreeNode?): Int {
    if (root == null) return 0
    var sum = 0
    //左
    var leftValue = sumOfLeftLeaves(root.left)
    //右
    var rightValue = sumOfLeftLeaves(root.right)
    //mid
    //判断左子叶
    if (root.left != null && root.left.left == null && root.left.right == null) {
        midValue = root.left.value
    }

    sum = midValue + leftValue + rightValue
    return sum
}

513.找树左下角的值(easy)

要点分析

使用层序遍历更加适合，只需要记录最后一行第一个节点的数值即可(如果是右下角则是最后一个最后一个节点)

代码

fun findBottomLeftValue(root: TreeNode?): Int {
    var queue = LinkedList<TreeNode>()
    var result = 0
    queue.offer(root)
    while(!queue.isEmpty()){
        var size = queue.size
        fro(i in 0..size-1){
            var curNode = queue.pop()
            //记录第一个数据即可
            if(i==0) result = curNode.`val`
            if(curNode.left != null) queue.offer(curNode.left)
            if(curNode.right != null) queue.offer(curNode.right)
        }
    }
    return result
}

112. 路径总和等于某个值(easy)

描述

说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树，以及目标和 sum = 22，

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

要点分析

遍历从根节点到子节点的路径是否满足目标和，采用逐渐递减的方式直到0说明找到路径，使用递归比较好理解

代码

fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
    if (root == null) return false
    var targetSum = targetSum
    targetSum -= root.`val`
    //叶子节点 开始做判断
    if (root.left == null && root.right == null) return targetSum == 0

    //左边
    if (root.left != null) {
        val isFindLeft = hasPathSum(root.left, targetSum)
        if (isFindLeft) return true
    }
    //右边
    if (root.right != null) {
        val isFindRight = hasPathSum(root.right, targetSum)
        if (isFindRight) return true
    }
    return false
}

113. 路径总和II(mid)

描述

112 路径总和只是需要判断是否存在路径即可，本题上升一下难度，需要记录路径

要点分析

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。难点在于回溯节点的记录，不过还是可以通过深度优先遍历来解决

代码

class Solution {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Deque<Integer> path = new LinkedList<Integer>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return ret;
    }

    public void dfs(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        path.offerLast(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0) {
            ret.add(new LinkedList<Integer>(path));
        }
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
        path.pollLast();
    }
}

算法题的一些集合

数组

704. 二分查找(easy)

27. 移除数组元素(easy)

977.有序数组的平方(easy)

209.(滑动窗口)长度最小的子数组(mid)

字符串

344. 反转字符串(easy)

541. 反转字符串II

剑指offer05 替换空格

哈希表

1. 两数之和(easy)

242.有效的字母异位数(easy)

349. 两个数组的交集(easy)

383. 赎金信

链表

203 移除链表元素(easy)

206.反转单链表(easy)

24. 两两交换链表中的元素(mid)

19. 删除链表倒数第N个节点(easy)

142.环形链表(mid)

二叉树

144. (DFS)二叉树前中后遍历(easy)

145. 二叉树后序遍历

146. 二叉树中序遍历

102.(BFS)二叉树层序遍历(mid）

226. 翻转二叉树(easy)

101. 对称二叉树(easy)

104. 二叉树的最大深度(easy)

111. 二叉树的最小深度(easy)

257.二叉树的所有路径(mid)

404.左叶子之和(easy)

513.找树左下角的值(easy)

112. 路径总和等于某个值(easy)

113. 路径总和II(mid)

资料区