algorithms►leetcode

019-子结构判断

子结构判断

子结构判断是算法设计中常见的问题类型，主要用于确定一个结构是否包含在另一个结构中

1. 字符串子序列判断

问题描述

判断字符串s是否是字符串t的子序列（子序列可以不连续但顺序必须一致）

解法（双指针法）

1
2
3
4
5
6
7
8
9
10
function isSubsequence(s, t) {
    let i = 0, j = 0;
    while (i < s.length && j < t.length) {
        if (s[i] === t[j]) {
            i++;
        }
        j++;
    }
    return i === s.length;
}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

2. LCR143.树的子树判断

问题描述

给定两棵二叉树 tree1 和 tree2，判断 tree2 是否以 tree1 的某个节点为根的子树具有相同的结构和节点值 。 注意，空树不会是以 tree1 的某个节点为根的子树具有相同的结构和节点值 。

解法（递归+DFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function isSubtree(root, subRoot) {
    if (!root) return false;
    return isSameTree(root, subRoot) || 
           isSubtree(root.left, subRoot) || 
           isSubtree(root.right, subRoot);
}

function isSameTree(p, q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    return p.val === q.val && 
           isSameTree(p.left, q.left) && 
           isSameTree(p.right, q.right);
}

复杂度分析

  • 时间复杂度：O(mn)，m和n分别是两树的节点数
  • 空间复杂度：O(h)，h为树的高度

3. 数组子数组判断

问题描述

判断数组subArr是否是数组arr的连续子数组

解法（滑动窗口）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function isSubarray(arr, subArr) {
    const n = arr.length, m = subArr.length;
    if (m > n) return false;
    
    for (let i = 0; i <= n - m; i++) {
        let match = true;
        for (let j = 0; j < m; j++) {
            if (arr[i + j] !== subArr[j]) {
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    return false;
}

优化解法（KMP算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function isSubarrayKMP(arr, subArr) {
    // 构建部分匹配表
    function buildLPS(pattern) {
        const lps = [0];
        let len = 0, i = 1;
        while (i < pattern.length) {
            if (pattern[i] === pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len !== 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    const lps = buildLPS(subArr);
    let i = 0, j = 0;
    while (i < arr.length) {
        if (arr[i] === subArr[j]) {
            i++;
            j++;
            if (j === subArr.length) return true;
        } else {
            if (j !== 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return false;
}

复杂度分析

  • 滑动窗口：O(mn)
  • KMP算法：O(m+n)

4. 图的子图判断

问题描述

判断图H是否是图G的子图（同构问题）

解法（回溯法）

1
2
3
4
5
6
7
8
9
10
11
12
function isSubgraph(G, H) {
    // 简化版实现思路
    // 1. 检查顶点数和边数
    if (H.vertices.length > G.vertices.length) return false;
    if (H.edges.length > G.edges.length) return false;
    
    // 2. 尝试所有可能的顶点映射
    // 实际实现需要使用回溯算法尝试所有可能的映射
    // 这里省略具体实现代码
    
    return backtrackingCheck(G, H);
}

5. 常见问题变种

变种1：判断子序列出现次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function numDistinct(s, t) {
    const m = s.length, n = t.length;
    const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
    
    for (let i = 0; i <= m; i++) dp[i][0] = 1;
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s[i-1] === t[j-1]) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    
    return dp[m][n];
}

变种2：带通配符的子序列匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function isMatch(s, p) {
    const m = s.length, n = p.length;
    const dp = Array.from({length: m+1}, () => new Array(n+1).fill(false));
    dp[0][0] = true;
    
    for (let j = 1; j <= n; j++) {
        if (p[j-1] === '*') {
            dp[0][j] = dp[0][j-1];
        }
    }
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j-1] === s[i-1] || p[j-1] === '?') {
                dp[i][j] = dp[i-1][j-1];
            } else if (p[j-1] === '*') {
                dp[i][j] = dp[i][j-1] || dp[i-1][j];
            }
        }
    }
    
    return dp[m][n];
}

总结

子结构判断问题的核心在于：

  1. 明确子结构的定义（连续/非连续）
  2. 选择合适的算法策略（双指针、动态规划、回溯等）
  3. 考虑边界条件和优化空间

不同场景下的子结构判断需要采用不同的方法，理解各种数据结构的特性是解决这类问题的关键。

algorithms►leetcode

020-二叉树展开为链表（递归）

二叉树展开为链表

问题描述

给定一个二叉树的根节点 root，要求将二叉树 原地（in-place） 展开为一个 单链表，展开后的单链表应该与二叉树的 先序遍历 顺序相同，且每个节点的 右子指针 指向链表中的下一个节点，左子指针始终为 null。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
输入:
    1
   / \
  2   5
 / \   \
3   4   6

输出:
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

方法一：递归展开（非原地）

思路

  1. 先序遍历 二叉树，将节点按顺序存入一个列表。
  2. 遍历列表，将每个节点的左指针设为 null，右指针指向下一个节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var flatten = function(root) {
    if (!root) return;
    
    const nodes = [];
    const preorder = (node) => {
        if (!node) return;
        nodes.push(node);
        preorder(node.left);
        preorder(node.right);
    };
    
    preorder(root); // 先序遍历，存储节点
    
    for (let i = 0; i < nodes.length - 1; i++) {
        nodes[i].left = null;
        nodes[i].right = nodes[i + 1];
    }
};

复杂度分析

  • 时间复杂度：O(n)，遍历所有节点两次（先序遍历 + 链表构建）。
  • 空间复杂度：O(n)，需要存储所有节点。

方法二：原地展开（递归）

思路

  1. 递归展开左右子树。
  2. 将左子树插入到右子树的位置，并 将原来的右子树接在左子树的最右节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var flatten = function(root) {
    if (!root) return;
    
    flatten(root.left);  // 展开左子树
    flatten(root.right); // 展开右子树
    
    const left = root.left;
    const right = root.right;
    
    root.left = null;    // 左指针置空
    root.right = left;   // 将左子树作为右子树
    
    // 找到当前右子树（原左子树）的最右节点
    let p = root;
    while (p.right) {
        p = p.right;
    }
    p.right = right;    // 将原右子树接在后面
};

复杂度分析

  • 时间复杂度：O(n)，每个节点被访问一次。
  • 空间复杂度：O(h)，递归栈的深度（h 为树高）。

方法三：原地展开（迭代 + Morris遍历）

思路

利用 Morris遍历 的思想，在遍历过程中直接修改指针，避免递归栈空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var flatten = function(root) {
    let curr = root;
    while (curr) {
        if (curr.left) {
            // 找到左子树的最右节点
            let predecessor = curr.left;
            while (predecessor.right) {
                predecessor = predecessor.right;
            }
            
            // 将右子树接到左子树的最右节点
            predecessor.right = curr.right;
            // 将左子树移到右子树位置
            curr.right = curr.left;
            curr.left = null;
        }
        curr = curr.right;
    }
};

复杂度分析

  • 时间复杂度：O(n)，每个节点被访问最多两次。
  • 空间复杂度：O(1)，仅使用常数级额外空间。

分步图解（以示例二叉树为例）

初始二叉树
1
2
3
4
5
     1
   /   \
  2     5
 / \     \
3   4     6
步骤 1：初始化
  • curr 指向根节点 1。
  • 检查 curr.left（2）存在，进入处理逻辑。
步骤 2：找到左子树的最右节点
  • predecessor 从 2 开始，向右走到 4（因为 4.right 为 null）。
1
2
3
4
5
6
7
8
     1
   /   \
  2     5
 / \     \
3   4     6
     ^
     |
 predecessor
步骤 3：重组指针

1.将右子树（5）挂到 predecessor 的右指针：

1
2
3
4
5
6
7
8
9
10
     1
   /   
  2     
 / \     
3   4
     \ 
      5
       \
        6

2. **将左子树（`2`）移到 `curr` 的右指针，左指针置空：

   1
    \
     2
    / \
   3   4
        \
         5
          \
           6
步骤 4：移动 curr
  • curr 向右移动到 2（原左子树的根节点）。
  • 重复上述过程：
    1. predecessor 从 3 开始，向右走到 3（因为 3.right 为 null）。
    2. 将 2 的右子树（4）挂到 3 的右指针：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      1
       \
        2
       / 
      3   
       \
        4
         \
          5
           \
            6
    3. 将左子树（3）移到 2 的右指针，左指针置空：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      1
       \
        2
         \
          3
           \
            4
             \
              5
               \
                6

代码逐行解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var flatten = function(root) {
    let curr = root;
    while (curr) {
        if (curr.left) {
            // 1. 找到左子树的最右节点
            let predecessor = curr.left;
            while (predecessor.right) {
                predecessor = predecessor.right;
            }
            
            // 2. 将右子树挂到最右节点
            predecessor.right = curr.right;
            
            // 3. 将左子树移到右子树位置
            curr.right = curr.left;
            curr.left = null;
        }
        // 4. 移动到下一个节点
        curr = curr.right;
    }
};
代码行 作用
let curr = root 初始化当前节点为根节点
if (curr.left) 检查是否存在左子树
predecessor = curr.left 从左子树的根节点开始
while (predecessor.right) 找到左子树的最右节点
predecessor.right = curr.right 将右子树接到最右节点
curr.right = curr.left 左子树变为右子树
curr.left = null 左指针置空
curr = curr.right 移动到处理后的下一个节点

为什么能保证正确性？

  1. 先序遍历顺序：
    • 每次将左子树移到右侧，保证了 根 -> 左 -> 右 的顺序。
  2. 指针修改的安全性：
    • predecessor 的右指针原本是 null，临时存储原右子树不会丢失信息。
  3. 终止条件：
    • 当 curr 移动到叶子节点时（curr.right === null），循环结束。

复杂度分析

操作 时间复杂度 空间复杂度
遍历所有节点 O(n) -
查找 predecessor 每个节点最多被访问两次 -
总计 O(n) O(1)

总结

  • 适用场景：需要原地修改且空间限制严格时。
  • 关键技巧：利用空闲指针（叶子节点的右指针）临时存储右子树。
  • 对比递归：避免了递归栈空间，适合深层树结构。

方法对比

方法 时间复杂度 空间复杂度 特点
递归（非原地） O(n) O(n) 简单直观，但需要额外空间
递归（原地） O(n) O(h) 原地修改，递归栈可能溢出
迭代（Morris） O(n) O(1) 最优解，无递归栈问题

关键点总结

  1. 先序遍历顺序：展开后的链表必须与先序遍历顺序一致。
  2. 原地修改：直接修改指针，不新建数据结构。
  3. Morris遍历：通过修改指针实现 O(1) 空间复杂度。

最终推荐代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 方法三：迭代（Morris遍历）
var flatten = function(root) {
    let curr = root;
    while (curr) {
        if (curr.left) {
            let predecessor = curr.left;
            while (predecessor.right) {
                predecessor = predecessor.right;
            }
            predecessor.right = curr.right;
            curr.right = curr.left;
            curr.left = null;
        }
        curr = curr.right;
    }
};