Leetcode 652. 寻找重复的子树(序列化 + 哈希表)

问题描述

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

Example

输入：[1,2,3,4,null,2,4,null,null,4]

输出:[[2,4],[4]]

思路

对于一棵树的子树间的匹配问题，可以采用序列化 + 哈希表的方式来求解。通过对树的序列化，并使用哈希表记录对应序列的出现次数。若当前节点 root 的序列化在哈希表中出现且仅出现过一次，则 root 就是我们要找的重复子树

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    unordered_map<string, int> table;
    string helper(TreeNode* root, vector<TreeNode*>& ans){
        if(root == nullptr)
            return "#";
        string tmp = to_string(root->val) + " " + helper(root->left, ans) + " " + helper(root->right, ans);
        if(table[tmp] == 1){
            ans.push_back(root);
        }
        ++table[tmp];
        return tmp;
    }
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        vector<TreeNode*> ans;
        helper(root, ans);
        return ans;
    }
};

执行结果： 76 ms, 49.6 MB

展开全文 >>

Leetcode 450. 删除二叉搜索树中的节点(BST的删除问题)

问题描述

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

一般来说，删除节点可分为两个步骤：

  • 首先找到需要删除的节点；
  • 如果找到了，删除它。

说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

Example

root = [5,3,6,2,4,null,7]

key = 3

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

另一个正确答案是 [5,2,6,null,4,null,7], 如下图所示。

题目链接：450. 删除二叉搜索树中的节点 (难度：中等)

思路

从题目描述中可知，我们需要做的事情有两个：找到节点和删除节点。我们考虑删除当前节点的情况：

  • 若当前节点是叶节点，则直接删除
  • 若当前节点的左右孩子中有一棵为空，则用另一个子树代替当前节点
  • 若当前节点的左右孩子均非空，我们统一将左子树作为根节点，并将右子树挂到左子树的最右结点的右端

其中，第一种情况是第二种情况的特例

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == NULL)
            return NULL;
        if(root->val == key){
            if(root->left && root->right){
                TreeNode* tmp = root->left;
                while(tmp->right){
                    tmp = tmp->right;
                }
                tmp->right = root->right;
                return root->left;
            }
            return root->right == NULL ? root->left : root->right;
        }else if(root->val < key){
            root->right = deleteNode(root->right, key);
        }else{
            root->left = deleteNode(root->left, key);
        }
        return root;
    }
};

执行结果：64 ms，32.5 MB

展开全文 >>

Leetcode 1104. 二叉树寻路（数学规律+位运算）

问题描述

在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。

如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；

而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。

给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。

  • 注意：1 <= label <= 10^6

Example

示例1：

输入：label = 14

输出：[1,3,4,14]

示例2：

输入：label = 26

输出：[1,2,6,10,26]

思路

从题目中的描述可以看出，我们只需要对一棵拥有无限节点的完全二叉树进行如下操作，就可以得到题目当中所描述的二叉树(以下简称树)：以根节点所在层为第1 层，对于偶数层进行翻转，奇数层保持不变。那么要解决这个问题，我们需要找到题目当中的树和一棵完全二叉树之间节点的对应关系：

设 f(x, k) 代表树中第 k 层节点 x 的父节点，则有以下两种考虑：

代码

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
class Solution {
public:
    void helper(int x, int k, vector<int>& ans){
        if(k == 1){
            ans.push_back(x);
            return;
        }
        if(k & 1){
            int tmp = (1 << k - 1) + (1 << k - 2) - 1;
            helper(tmp - (x >> 1), k - 1, ans);
            ans.push_back(x);
        }else{
            int tmp = (1 << k) + (1 << k - 1) - 1 - x;
            helper(tmp >> 1, k - 1, ans);
            ans.push_back(x);
        }
    }
    vector<int> pathInZigZagTree(int label) {
        vector<int> ans;
        int level = 0, tmp = label;
        while(tmp){
            tmp >>= 1;
            ++level;
        }
        helper(label, level, ans);
        return ans;
    }
};

执行结果： 4 ms, 6.5 MB

改进思路

在题目的评论区当中，我看到了一种非常高效且优雅简洁的实现方式。对于一棵完全二叉树，每个节点的编号都可以和一个二进制数一一对应。而将某一层的节点翻转，只需要对该层的每个节点 X，保留最高位(保留最高位确保给节点所在的层次不发生变化)，再将其他位全部按位取反，即可将该层代码翻转。

举个例子：

如示例 1 当中那样，14 的二进制表示为 1110b，位于第 4 层，我们要找到 14 对应的第 3 的元素，也就是 111b(右移一位即可做到)，然后对第 3 层进行翻转，即 111 ^ 011 = 100(保留最高位，剩下位取反)，也就是第 3 层的 4。对 4 进行相同的操作，又可以得到 4 对应第 2 层的节点 3.

这一做法好处非常明显：

1.它和题目当中所描述的操作是完全一致的

2.前面找规律的方法，需要结合节点所在层次进行计算，而第二种方法无需考虑层次，因为它从第二层开始，每一层都进行翻转，则显然最终的结果只有偶数层发生了翻转，而奇数层的翻转次数始终为偶数，也就相当于没有翻转。

从这个思路当中可以知道两个结论，能够借鉴在未来的题目当中：

  • 完全二叉树的节点编号可以和二进制编码相结合，其中高位保证了对应的层次
  • 对二叉树的某层节点进行翻转或者求对称节点，可以通过和对应层掩码来进行异或的方式获得，这种高效简洁而且能够叠加使用。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void helper(int x, int k, vector<int>& ans){
        if(k == 1){
            ans.push_back(x);
            return;
        }
        // 此处由于 x 右移了 1 位，所以是 k - 2，而不是 k - 1
        int tmp = (x >> 1) ^ ((1 << k - 2) - 1);
        helper(tmp, k - 1, ans);
        ans.push_back(x);
    }
    vector<int> pathInZigZagTree(int label) {
        vector<int> ans;
        int level = 0, tmp = label;
        while(tmp){
            tmp >>= 1;
            ++level;
        }
        helper(label, level, ans);
        return ans;
    }
};

执行结果： 0 ms, 6.5 MB

展开全文 >>

Leetcode 529. 扫雷游戏(二维矩阵上的DFS)

问题描述

让我们一起来玩扫雷游戏！

给定一个代表游戏板的二维字符矩阵。 ‘M’ 代表一个未挖出的地雷，’E’ 代表一个未挖出的空方块，’B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（’1’ 到 ‘8’）表示有多少地雷与这块已挖出的方块相邻，’X’ 则表示一个已挖出的地雷。

现在给出在所有未挖出的方块中（’M’或者’E’）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：

  • 如果一个地雷（’M’）被挖出，游戏就结束了- 把它改为 ‘X’。
  • 如果一个没有相邻地雷的空方块（’E’）被挖出，修改它为（’B’），并且所有和其相邻的方块都应该被递归地揭露。
  • 如果一个至少与一个地雷相邻的空方块（’E’）被挖出，修改它为数字（’1’到’8’），表示相邻地雷的数量。
  • 如果在此次点击中，若无更多方块可被揭露，则返回面板。

Example

输入:

[[‘E’, ‘E’, ‘E’, ‘E’, ‘E’],

[‘E’, ‘E’, ‘M’, ‘E’, ‘E’],

[‘E’, ‘E’, ‘E’, ‘E’, ‘E’],

[‘E’, ‘E’, ‘E’, ‘E’, ‘E’]]

Click : [3,0]

输出:

[[‘B’, ‘1’, ‘E’, ‘1’, ‘B’],

[‘B’, ‘1’, ‘M’, ‘1’, ‘B’],

[‘B’, ‘1’, ‘1’, ‘1’, ‘B’],

[‘B’, ‘B’, ‘B’, ‘B’, ‘B’]]

示例解释

Note

  • 输入矩阵的宽和高的范围为 [1,50]。
  • 点击的位置只能是未被挖出的方块 (‘M’ 或者 ‘E’)，这也意味着面板至少包含一个可点击的方块。
  • 输入面板不会是游戏结束的状态（即有地雷已被挖出）。
  • 简单起见，未提及的规则在这个问题中可被忽略。例如，当游戏结束时你不需要挖出所有地雷，考虑所有你可能赢得游戏或标记方块的情况。

题目链接：529. 扫雷游戏 (难度:中等)

思路

从题目的描述上来看，这应当属于是一个二维矩阵的上的深度优先搜索问题。我们需要从题目的描述以及示例当中发现游戏的规则，主要有以下两个：

  • 如果 board[x][y] 周围的 8 个格子当中有 M 颗地雷，我们需要将 board[x][y] 置为 M，同时停止递归直接返回。(这样做确保不越过数字边界，踩到地雷。数字边界就是示例解释中的 ‘1’)
  • 若 board[x][y] 的周围没有雷，直接将 board[x][y] 置为 ‘B’, 同时递归处理 board[x][y] 周围的 8 个格子。

我们先试探性地将 board[x][y] 置为 ‘B’，然后进行两次循环，第一次统计周围雷数，第二次更新 board[x][y] 的地雷信息。具体过程见代码

代码

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
class Solution {
public:
    int direction[8][2] = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
    int row = 0, col = 0;
    void dfs(vector<vector<char>>& board, int x, int y){
        board[x][y] = 'B';
        int mine = 0;
        for(int i = 0;i < 2;++i){
            for(int j = 0;j < 8;++j){
                int nx = x + direction[j][0];
                int ny = y + direction[j][1];
                if(nx < 0 || nx >= row || ny < 0 || ny >= col || board[nx][ny] == 'B' || isdigit(board[nx][ny]))
                    continue;
                if(i == 0 && board[nx][ny] == 'M')
                    ++mine;
                if(i == 1){
                    if(mine == 0){
                        dfs(board,nx,ny);
                    }else{
                        board[x][y] = '0' + mine;
                        return;
                    }
                }
            }
        }        
    }
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int x = click[0], y = click[1];
        row = board.size(), col = board[0].size();
        if(board[x][y] == 'M'){
            board[x][y] = 'X';
        }else if(board[x][y] == 'E'){
            dfs(board,x,y);
        }
        return board;
    }
};

执行结果： 64 ms, 16 MB

展开全文 >>

Leetcode 306. 累加数(回溯算法+子串分割问题)

问题描述

累加数是一个字符串，组成它的数字可以形成累加序列。

一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。

给定一个只包含数字 ‘0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是累加数。

说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

**进阶:**你如何处理一个溢出的过大的整数输入?

Example

输入: “199100199”

输出: true

解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

题目链接：306. 累加数 (难度：中等)

思路

同问题 Leetcode 842. 将数组拆分成斐波那契序列 相同，这个问题同样可视为是对子串分割问题的一个扩展。在子串分割问题的框架下，我们需要明确约束条件以及优化条件。在这个问题下，约束条件主要有两个：

  • 分割出来的子串必须满足斐波那契序列的定义
  • 对于数字而言，不允许出现前导零。换言之，如果当前模式串 s 满足 s[0] = ‘0’，则 s[0] 开头的合法子串有且仅有 0 一个。

由于在子串分割问题当中，我们需要逐步递增地尝试枚举子串长度，而在这个问题当中，若满足 F[i] + F[i+1] == F[i+2]，则显然子串 F[i+2] 的长度必定大于或等于 F[i] 或 F[i+1] 中的最长者，可以利用这一事实来优化枚举的长度。这里为了兼容进阶的要求，我们采用unsigned long long 类型防止溢出，最高数位可达 20 位

代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
public:
    typedef unsigned long long ull;
    vector<ull> ans;
    string MAX = "18446744073709551615";
    bool dfs(string& s, int fib_size, vector<int>& bit_len){
        if(s.size() == 0){
            return true;
        }
        if(s[0] == '0'){
            // 若 s[0] = '0'，且 0 本身不满足斐波那契序列的定义，则返回 false
            if(fib_size > 1 && ans[fib_size-1] + ans[fib_size-2] != 0){
                return false;
            }
            string next = s.substr(1);
            ans.push_back(0);
            bit_len.push_back(1);
            if(dfs(next, fib_size + 1, bit_len)){
                return true;
            }
            ans.pop_back();
            bit_len.pop_back();
        }else{
            if(fib_size > 1){
                int len = max(bit_len[fib_size -1], bit_len[fib_size - 2]);
                //剩余子串长度不够拆分，则返回 false
                if(s.size() < len){
                    return false;
                }
                for(int i = len;i < min(21,len + 2);++i){
                    string cur = s.substr(0,i);
                    if(cur.size() == 20 && cur > MAX){
                        return false;
                    }
                    ull fib = stoul(cur);
                    // 这里采用减法的方式可以防止加法溢出报错
                    if(ans[fib_size - 1] <= ULLONG_MAX - ans[fib_size - 2] && ans[fib_size - 1] + ans[fib_size - 2] == fib){
                        string next_fib = s.substr(i);
                        ans.push_back(fib);
                        bit_len.push_back(i);
                        if(dfs(next_fib, fib_size + 1, bit_len)){
                            return true;
                        }
                        ans.pop_back();
                        bit_len.pop_back();
                    }
                }
            }else{
               //由于斐波那契序列中元素的个数不低于 3 个当分割出来的子串个数不足两个时，
                //对子串的枚举长度不能超过原串长度的一半，否则必定无法分割成 3 个子串
                int max_len = s.size() >> 1;
                for(int i = 1;i <= min(20,max_len);++i){
                    string cur = s.substr(0,i);
                    if(cur.size() == 20 && cur > MAX){
                        return false;
                    }
                    string next = s.substr(i);
                    ull fib_cur = stoul(cur);
                    ans.push_back(fib_cur);
                    bit_len.push_back(i);
                    if(dfs(next, fib_size + 1, bit_len)){
                       return true; 
                    }
                    ans.pop_back();
                    bit_len.pop_back();
                }
            }
        }
        return false;
    }
    bool isAdditiveNumber(string num) {
        int len = num.size();
        if(len < 3) return false;
        vector<int> bit_len;
        return dfs(num, 0, bit_len);
    }
};

执行结果： 0 ms，6.4 MB

展开全文 >>

Leetcode 1080. 根到叶路径上的不足节点(后序遍历 + 树的删除问题)

问题描述

给定一棵二叉树的根 root，请你考虑它所有 从根到叶的路径：从根到任何叶的路径。（所谓一个叶子节点，就是一个没有子节点的节点）

假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为「不足节点」，需要被删除。

请你删除所有不足节点，并返回生成的二叉树的根。

Example

示例1

输入

输入：root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1

输出：[1,2,3,4,null,null,7,8,9,null,14]

输出

示例2

输入

输入：root = [5,-6,-6], limit = 0

输出：[]

题目链接：1080. 根到叶路径上的不足节点 (难度:中等)

思路

对于二叉树的删除，我们一般有两种方式：

  • 利用父节点对左右孩子进行删除
  • 直接删除自身并返回(需要采用引用的方式删除)

从测试用例 2 上，我们可以看出在某些情况下，连根节点都是需要删除的。由于根节点没有父节点，故我们采用第二种方式，利用回溯的方式删除自身节点。同时为了避免像链表一样出现断链，我们采用后序遍历的方式进行删除。既然已经明确题目的主要任务(删除节点)以及删除方式后，接下来只需要找到删除的规则即可解决问题。

不妨假设函数 bool dfs(X, sum, limit) 为判断 root 是否为不足节点的函数，其中 sum 记录从根节点 root 到 X 的父结点的路径和，显然若出现以下三种情况，则应当删除：

1、若 X 的左孩子节点是不足节点，且右孩子也是不足节点，则 X 也是不足节点

2、若 X 的左孩子节点是不足节点，且右孩子为空，则 X 也是不足节点

3、若 X 的左孩子为空，且右孩子是不足节点，则 X 也是不足节点

递归的 Base Case 为：若 X == NULL 则返回 sum < limit

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool dfs(TreeNode* &root, int sum, int limit){
        if(root == NULL)
            return sum < limit;
        bool l_tree = dfs(root->left, sum + root->val, limit);
        if(l_tree && root->right == NULL){
            root = NULL;
            return true;
        }
        bool r_tree = dfs(root->right, sum + root->val, limit);
        if((r_tree && root->left == NULL) || (l_tree && r_tree)){
            root = NULL;dang
            return true;
        }
        return l_tree && r_tree;
    }
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        dfs(root, 0, limit);
        return root;
    }
};

执行结果： 104 ms, 32.8 MB

展开全文 >>

Leetcode 951. 翻转等价二叉树(树的匹配问题)

问题描述

我们可以为二叉树 T 定义一个翻转操作，如下所示：选择任意节点，然后交换它的左子树和右子树。

只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转等价于二叉树 Y。

编写一个判断两个二叉树是否是翻转等价的函数。这些树由根节点 root1 和 root2 给出。

Example

输入：root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]

输出：true

解释：我们翻转值为 1，3 以及 5 的三个节点。

Note

  • 每棵树最多有 100 个节点。
  • 每棵树中的每个值都是唯一的、在 [0, 99] 范围内的整数。

题目链接：951. 翻转等价二叉树 (难度:中等)

思路

对于这个问题，我们依然采用遍历的方式来判断。为了便于将问题描述清楚，我们在这个地方定义 3 种状态：

  • 直接等价：root1 和 root2 无需经过翻转就等价 (对 root1 和root2均采用 LR 的顺序遍历)
  • 翻转等价：root1 和 root2 经过翻转之后等价(对 root1 采用 LR顺序遍历，对 root2 则采用 RL 的顺序遍历)
  • 不等价

按照题目定义，我们显然知道以下信息：

  1. 两棵空树是直接等价的
  2. 两棵树中仅有一棵空树，或者 root1->val != root2->val，则显然 root1 和 root2 是不等价的
  3. 对于除前两种情况以外的情况，如果 root1 和 root2 是等价的，则要么是翻转等价，要么是直接等价，二者必属其一，是逻辑或的关系。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool flipEquiv(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 (flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right)) || (flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left));
    }
};

执行结果： 8 ms，12.1 MB

展开全文 >>

Leetcode 1367. 二叉树中的列表(树的匹配问题)

问题描述

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

Example

输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]

输出：true

解释：树中蓝色的节点构成了与链表对应的子路径。

Note

  • 二叉树和链表中的每个节点的值都满足 1 <= node.val <= 100 。
  • 链表包含的节点数目在 1 到 100 之间。
  • 二叉树包含的节点数目在 1 到 2500 之间。

题目链接：1367. 二叉树中的列表 (难度:中等)

思路

为了完成二叉树和链表的匹配任务，我们需要对 root 中的每一棵子树进行匹配。因此，我们需要实现两个函数，一个用于匹配当前以 root 为根的子树 (helper)，另一个函数用于枚举整棵树中的所有子树(isSubPath)。由于路径本身指定了从上到下，这两个函数均采用先序遍历的方式进行处理

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool helper(ListNode* head, TreeNode* root){
        if(head == NULL)
            return true;
        if(root == NULL)
            return false;
        if(root->val == head->val){
            return helper(head->next, root->left) || helper(head->next, root->right);
        }
        return false;
    }
    bool isSubPath(ListNode* head, TreeNode* root) {
        if(head == NULL)
            return true;
        if(root == NULL)
            return false;
        if(helper(head, root))
            return true;
        return isSubPath(head, root->left) || isSubPath(head, root->right);
    }
};

执行结果： 52 ms， 22.1 MB

相关习题：面试题26. 树的子结构

展开全文 >>

Leetcode 889. 根据前序和后序遍历构造二叉树(分治算法)

问题描述

返回与给定的前序和后序遍历匹配的任何二叉树。

pre 和 post 遍历中的值是不同的正整数。

Example

输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]

输出：[1,2,3,4,5,6,7]

Note

  • 1 <= pre.length == post.length <= 30
  • pre[] 和 post[] 都是 1, 2, …, pre.length 的排列
  • 每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。

题目链接：889. 根据前序和后序遍历构造二叉树 (难度:中等)

思路

在树的四序遍历当中，先序、后序和层序能够提供树中节点的父子关系，而中序则能够提供树中节点的左右关系，因此，只有中序+先序、中序+后序、中序+层序能够唯一确定一棵树，而先序+后序可以确定的树不唯一。当答案不唯一时，由于后序顺序为 LRN，先序顺序为 NLR，当某个节点只有一个孩子时，无法从序列中确定是左子树还是右子树，为了方便起见，我们统一将其定义为左子树

对于这个问题采取分治法，先确定根节点，然后将序列分割为左右子树的序列，各个击破即可。在实现上，使用了 unordered_map 对序列进行缓存，既可以提高递归时的查找效率，同时也避免了查找过程当中的越界情况。具体过程可见下图：

左右子树同，则统一当作左子树处理

左右子树不同，则分治处理左右子树

代码

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
class Solution {
public:
    unordered_map<int, int> pre_table;
    unordered_map<int, int> post_table;
    TreeNode* buildTree(vector<int>& pre, int l_pre, int r_pre, vector<int>& post, int l_post, int r_post){
        if(l_pre > r_pre)
            return NULL;
        TreeNode* root = new TreeNode(pre[l_pre]);
        if(l_post == r_post){
            return root;
        }
        int l_root = pre[l_pre + 1];
        int r_root = post[r_post - 1];
        if(l_root == r_root){
            root->left = buildTree(pre, l_pre + 1, r_pre, post, l_post, r_post - 1);
            root->right = NULL;
        }else{
            int r_pre_root = pre_table[r_root];
            int l_post_root = post_table[l_root];
            root->left = buildTree(pre, l_pre + 1, r_pre_root - 1, post, l_post, l_post_root);
            root->right = buildTree(pre, r_pre_root, r_pre, post, l_post_root + 1, r_post - 1);
        }
        return root;
    }
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        int len = pre.size();
        for(int i = 0;i < len;++i){
            pre_table[pre[i]] = i;
            post_table[post[i]] = i;
        }
        return buildTree(pre, 0, len - 1, post, 0, len - 1);
    }
};

执行结果: 28ms, 27.6MB

相关文章：

展开全文 >>

Leetcode 979. 在二叉树中分配硬币(树的后序遍历)

问题描述

给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。

在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。

返回使每个结点上只有一枚硬币所需的移动次数。

Example

示例1

输入：[3,0,0]

输出：2

解释：从树的根结点开始，我们将一枚硬币移到它的左子结点上，一枚硬币移到它的右子结点上。

示例1

示例2

输入：[0,3,0]

输出：3

解释：从根结点的左子结点开始，我们将两枚硬币移到根结点上 [移动两次]。然后，我们把一枚硬币从根结点移到右子结点上。

Note：

1<= N <= 100

0 <= node.val <= N

题目链接：979. 在二叉树中分配硬币 (难度:中等)

思路

倒过来看这个问题，不要想着先从某个有硬币的节点处搬硬币到没有硬币的结点处，而是反过来，如果子节点没有硬币，那就先借给它一枚硬币，然后“子债父偿”，回溯到父结点时，清算欠款，留一枚硬币给父结点后，若有剩余硬币则统统没收，继续回溯父节点，直至遍历完全树。在这个思路中，我们采用先访问子节点，后访问父节点的形式，因此选择后序遍历。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int ans = 0;
    int dfs(TreeNode* root){
        if(root == NULL)
            return 0;
        int l_re = dfs(root->left);
        int r_re = dfs(root->right);
        ans += abs(l_re) + abs(r_re);
        return l_re + r_re + root->val - 1;
    }
    int distributeCoins(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

执行结果： 8 ms, 13.9 MB

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要涉及技术：
C++, 后端开发, lua语言
开源爱好者、Linux

热爱阅读，健身，旅游及美食

联系QQ:519788069