数据结构和算法是编程路上永远无法避开的两个核心知识点，本系列【算法题】旨在记录刷题过程中的一些心得体会，将会挑出LeetCode等最具代表性的题目进行解析，题解基本都来自于LeetCode官网（https://leetcode-cn.com/），本文是第七篇。

1.反转链表2（原第92题）

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

（1）知识点

链表

（2）解题方法

方法转自：https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/fan-zhuan-lian-biao-ii-by-leetcode/

方法：迭代链接反转

官方的递归解法是只交换链表的值，但是其实应该要交换节点的，这样才叫真正的反转啊。
参考官方评论下面的一个解法。
思想很简答，首先跑m个节点，找到起始节点，交换它和下一个节点，然后将再往后一个节点放到重排序的节点串的前面，以1->2->3->4->5->NULL, m = 2, n = 5为例：

• 初始状态：1(prev)->2(head)->3(head.next)->4->5->NULL
• 将head.next移动到prev后面：1(prev)->3->2(head)->4(head.next)->5->NULL
• 将head.next移动到prev后面：1(prev)->4->3->2(head)->5(head.next)->NULL
• 将head.next移动到prev后面：1(prev)->5->4->3->2(head)->NULL(head.next)
• 时间复杂度：O(n)，由于对长度 N的链表进行了一次遍历。
• 空间复杂度：O(1)，不需要额外的空间开销。

（3）伪代码

函数头：reverseBetween(ListNode* head, int m, int n)

方法：迭代链接反转

• 定义一个dummy节点
• 定义一个prev节点，它将等于位置为m的节点的前一个节点
• 第一次循环：当m > 1时，（prev后移，m和n递减）
• head=prev.next
• 第二次循环：当n > 0时，（将head.next移到prev后面，具体步骤：定义一个新节点tmp=head.next，head.next=tmp.next（至此tmp这个节点就被拿出来了），tmp.next=prev.next，prev.next=tmp）），n--）
• 返回dummy.next

（4）代码示例

public ListNode reverseBetween(ListNode head, int m, int n) {

    ListNode dummy = new ListNode(-1);
    ListNode prev = dummy;
    prev.next = head;
    while(m > 1){
        prev = prev.next;
        --m;
        --n;
    }
    head = prev.next;
    while(n > 1){
        ListNode temp = head.next;
        head.next = head.next.next;
        temp.next = prev.next;
        prev.next = temp;
        --n;
    }
    return dummy.next;
}

---

---

2.不同的二叉搜索树2（原第95题）

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出：
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \
3 2 1 1 3 2
/ / \
2 1 2 3

（1）知识点

二叉搜索树

（2）解题方法

方法转自：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode-solut/

方法：递归

二叉搜索树关键的性质是根节点的值大于左子树所有节点的值，小于右子树所有节点的值，且左子树和右子树也同样为二叉搜索树。因此在生成所有可行的二叉搜索树的时候，假设当前序列长度为 n，如果我们枚举根节点的值为 i，那么根据二叉搜索树的性质我们可以知道左子树的节点值的集合为 [1…i?1]，右子树的节点值的集合为 ][i+1…n]。而左子树和右子树的生成相较于原问题是一个序列长度缩小的子问题，因此我们可以想到用递归的方法来解决这道题目。
我们定义 generateTrees(start, end) 函数表示当前值的集合为 [start,end]，返回序列 [start,end] 生成的所有可行的二叉搜索树。按照上文的思路，我们考虑枚举 [start,end] 中的值 i 为当前二叉搜索树的根，那么序列划分为了 [start,i?1] 和 [i+1,end] 两部分。我们递归调用这两部分，即 generateTrees(start, i - 1) 和 generateTrees(i + 1, end)，获得所有可行的左子树和可行的右子树，那么最后一步我们只要从可行左子树集合中选一棵，再从可行右子树集合中选一棵拼接到根节点上，并将生成的二叉搜索树放入答案数组即可。

（3）伪代码

函数头：List generateTrees(int n)

方法：递归

• 略

（4）代码示例

public List<TreeNode> generateTrees(int n) {
    if(n == 0) return new LinkedList<>();
    return generate(1, n);
}

private List<TreeNode> generate(int start, int end){
    List<TreeNode> res = new LinkedList<>();
    if(start > end){
        res.add(null);
        return res;
    }
    for(int i = start; i <= end; ++i){
        List<TreeNode> lefts = generate(start, i-1);
        List<TreeNode> rights = generate(i+1, end);
        for(TreeNode left : lefts){
            for(TreeNode right : rights){
                TreeNode root = new TreeNode(i);
                root.left = left;
                root.right = right;
                res.add(root);
            }
        }
    }
    return res;
}

---

---

3.对称二叉树（原第101题）

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

（1）知识点

二叉树的遍历

（2）解题方法

方法转自：https://leetcode-cn.com/problems/symmetric-tree/solution/dui-cheng-er-cha-shu-by-leetcode-solution/

方法一：递归

我们可以构造两棵树，这两棵互为镜像，如何实现呢？其实只要遍历的时候一个永远从左边开始，一个永远从右边开始就行了。
我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，p 指针和 q 指针一开始都指向这棵树的根，随后 p 右移时 q 左移，p 左移时，q 右移。每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。

• 时间复杂度 : 这里遍历了这棵树，渐进时间复杂度为 O(n)。
• 空间复杂度 : 这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。

方法二：迭代

事实上，有递归的地方就有迭代，递归看起来更简洁，迭代则思路更加清晰。
这里和递归思路相同，也是构建两棵树，先入队两个树的根节点，然后出队比较，然后入队树1的左节点，树2的右节点，树1的右节点和树二的左节点。继续出队比较。

（3）伪代码

函数头：boolean isSymmetric(TreeNode root)

方法一：递归

• 比较简单，就是构造一个函数，参数是两个根节点，然后先序遍历分别检查树1的左节点是否等于树2的右节点，以及树1的右节点是否等于树2的左节点。

方法二：迭代

• 定义一个队列用于存储遍历时的节点queue
• 入队两棵树的根节点
• 第一重循环（queue不为空）
  • 出队两个元素u和v，比较
  • 入队u.left v.right u.right v.left

（4）代码示例

public boolean isSymmetric(TreeNode root) {
    return isSymmetric(root, root);
}

private boolean isSymmetric(TreeNode root1, TreeNode root2){
    if(root1 == null && root2 == null) return true;
    if(root1 == null || root2 == null) return false;
    if(root1.val != root2.val) return false;
    return isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left);
}

---

---

4.二叉树的锯齿形层序遍历（原第103题）

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

（1）知识点

二叉树的遍历

（2）解题方法

方法转自：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/solution/er-cha-shu-de-ju-chi-xing-ceng-ci-bian-li-by-leetc/

方法一：BFS

常规的层序遍历我们知道使用一个队列就能解决问题，但是这种奇数偶数层顺序不同的遍历就不能这么简单了，这里采用标准题解地下的一个评论的答案。
同样的，我们采用一个队列用来存储每个节点，但用一个链表来存放当前层的顺序，最后这个队列只用来实现层序，而链表来实现遍历（因为链表两遍都能插入）

• 时间复杂度 : O(n)，其中 n 是树中节点的数量。
• 空间复杂度 : O(n)，其中 n 是树中节点的数量。

方法二：DFS

DFS虽然没有BFS那么容易想到，但是也不难理解，因为这里要返回的是一个二维数组，每一行一个数组，那么我们就可以采用深度优先，通过记录层数然后决定在每个list前面或者后面插入元素。

• 时间复杂度 : O(n)，其中 n 是树中节点的数量。
• 空间复杂度：O(H)，其中 H 是树的高度。

（3）伪代码

函数头：List<List> zigzagLevelOrder(TreeNode root)

方法一：BFS

• 定义一个数组用于返回res
• 如果root=null，返回一个新数组
• 定义一个队列queue，根节点入队
• 定义一个level=0
• 第一重循环（当queue不为空）
  • 定义size为queue当前的size，
  • 定义一个临时的链表list，用于存储节点值
  • 第二重循环（i:0->size-1）：这里不直接用queue.size()的原因是循环中queue会不断入队，所以会出现死循环
    • queue出队一个元素head
    • 如果head.left不为空，queue入队；如果head.right不为空，queue入队
    • 如果level为偶数，list.add(head.val)，如果level为奇数，list.push(head.val)——核心步骤
  • res.add(list)
  • level++

方法二：DFS

包裹函数里面和BFS一样，判空，然后定义一个新数组调用DFS
函数void DFS(TreeNode node, int level, List<List> results)

• 如果level大于等于results的size，定义一个新list，把node.val添加进去，results.add(list)
• 否则，如果为偶数层，results.get(results.size()-1).add(node.val)，如果为奇数层，results.get(results.size()-1).push(node.val)
• node左边不为空，调用DFS(node.left, level+1, results)
• node右边不为空，调用DFS(node.right, level+1, results)

（4）代码示例

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if(root == null) return res;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    TreeNode curr;
    while(!queue.isEmpty()){
        int size = queue.size();
        res.add(new ArrayList<>());
        int level = res.size() - 1;
        for(int i = 0; i < size; ++i){
            curr = queue.poll();
            res.get(level).add(curr.val);
            if(curr.left != null) queue.offer(curr.left);
            if(curr.right != null) queue.offer(curr.right);
        }
        if(level%2 != 0){
            reverse(res.get(level));
        }
    }

    return res;
}


private void reverse(List<Integer> list){
    int left = 0;
    int right = list.size() - 1;
    while(left < right){
        int temp = list.get(left);
        list.set(left, list.get(right));
        list.set(right, temp);
        ++left;
        --right;
    }
}

---

---

5.有序链表转换二叉搜索树（原第109题）

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

（1）知识点

二叉树的遍历、双指针

（2）解题方法

方法转自：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-by-/

方法：递归+双指针

如果这个列表是一个普通的数组，那么可以通过下标找到中间点，然后以它为根构建。这个题是个链表，所以需要先用双指针法找到中间节点（方法就是快慢指针）。然后通过递归的方法，构建左右子树即可。

• 时间复杂度：O(NlogN)。假设链表包含 N 个元素，对于传入递归函数的每个列表，我们需要计算它的中间元素。对于一个大小为 N 的列表，需要 N/2 步找到中间元素，也就是花费 O(N) 的时间。我们对于原始数组的每一半都要同样的操作，看上去这是一个 O(N^2) 的算法，但仔细分析会发现比 O(N^2) 更高效。
• 空间复杂度：O(logN)。因为使用递归的方法，所以需要考虑递归栈的空间复杂度。对于一棵费平衡二叉树，可能需要 O(N) 的空间，但是问题描述中要求维护一棵平衡二叉树，所以保证树的高度上界为 O(logN)，因此空间复杂度为 O(logN)。

其他方法，一种是转成数组来做，那就和数组构建查找二叉树没差别了，另一个种方法是通过中序遍历的方法来构建二叉树，这个方法不太容易会想到。

（3）伪代码

函数头：TreeNode sortedListToBST(ListNode head)

方法：递归+双指针

• 调用findMiddle找到中间节点mid
• 定义根节点root=new TreeNode(mid.val)
• 如果head=mid，返回root
• root.left=sortedListToBST(head)
• root.right=sortedListToBST(mid.next)

定义一个用于找到中间点的函数findMiddle，用快慢指针，很简单。

（4）代码示例

public TreeNode sortedListToBST(ListNode head) {
    return buildTree(head, null);
}

public TreeNode buildTree(ListNode left, ListNode right) {
    if (left == right) {
        return null;
    }
    ListNode mid = getMedian(left, right);
    TreeNode root = new TreeNode(mid.val);
    root.left = buildTree(left, mid);
    root.right = buildTree(mid.next, right);
    return root;
}

public ListNode getMedian(ListNode left, ListNode right) {
    ListNode fast = left;
    ListNode slow = left;
    while (fast != right && fast.next != right) {
        fast = fast.next;
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

---

---