鲤鱼笔记

树：其他

2022-04-10 每日一题 LeetCode

# 0095. 不同的二叉搜索树 II (opens new window)

题目

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

解析

通过值在 l 到 r 这个范围内的节点构造二叉搜索树，可以先枚举根节点，假设当前枚举的根节点是 i，那么左子树就是从 l 到 i-1 这个范围内的节点去构造的；右子树是从 i+1 到 r 这部分节点构造的，这样就可以通过递归解决。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        return build(1, n);
    }

    vector<TreeNode*> build(int l, int r) {
        if (l > r) return {nullptr};
        vector<TreeNode*> ans;
        for (int i = l; i <= r; i++) {
            vector<TreeNode*> lnodes = build(l, i - 1);
            vector<TreeNode*> rnodes = build(i + 1, r);
            for (int j = 0; j < lnodes.size(); j++) {
                for (int k = 0; k < rnodes.size(); k++) {
                    TreeNode* root = new TreeNode(i);
                    root->left = lnodes[j];
                    root->right = rnodes[k];
                    ans.push_back(root);
                }
            }
        }
        return ans;
    }
};
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

# 0105. 从前序与中序遍历序列构造二叉树 (opens new window)

题目

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，同时保证无重复元素，请构造二叉树并返回其根节点。

解析

二叉树的根节点就是前序序列的第一个节点，这样就可以把中序序列拆分成两部分，根节点前面就是左子树，后面就是右子树，那么就知道了左右子树的节点数量，依此就可以对前序序列也进行拆分，这样左右子树的前序、中序序列都知道了，递归构建左右子树就可以了。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    unordered_map<int, int> pos;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; i++) pos[inorder[i]] = i;
        return build(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir) {
        if (pl > pr || il > ir) return nullptr;

        int k = pos[preorder[pl]] - il;

        TreeNode* root = new TreeNode(preorder[pl]);
        root->left = build(preorder, inorder, pl + 1, pl + k, il, il + k - 1);
        root->right = build(preorder, inorder, pl + k + 1, pr, il + k + 1, ir);

        return root;
    }
};
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

# 0106. 从中序与后序遍历序列构造二叉树 (opens new window)

题目

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

解析

后序序列的最后一个节点就是根节点，依此可以对两序列进行划分，得到左右子树的后序序列和中序序列，进而递归构建左右子树。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    unordered_map<int, int> pos;
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        for (int i = 0; i < n; i++) pos[inorder[i]] = i;
        return build(inorder, postorder, 0, n - 1, 0, n - 1);
    }

    TreeNode* build(vector<int>& inorder, vector<int>& postorder, int il, int ir, int pl, int pr) {
        if (il > ir || pl > pr) return nullptr;

        int k = pos[postorder[pr]] - il;

        TreeNode* root = new TreeNode(postorder[pr]);
        root->left = build(inorder, postorder, il, il + k - 1, pl, pl + k - 1);
        root->right = build(inorder, postorder, il + k + 1, ir, pl + k, pr - 1);

        return root;
    }
};
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

# 0114. 二叉树展开为链表 (opens new window)

题目

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

解析

从每个节点的左孩子向右找到最后一个节点，然后通过这部分子链将左子树合并到右子树上，直到每个节点都完成合并。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* cur = root;
        while (cur) {
            if (cur->left) {
                TreeNode* p = cur->left;
                while (p->right) p = p->right;
                p->right = cur->right;
                cur->right = cur->left;
                cur->left = nullptr;
            }
            cur = cur->right;
        }
    }
};
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

# 0116. 填充每个节点的下一个右侧节点指针 (opens new window)

题目

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
1
2
3
4
5
6

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

解析

通过从根节点不断向左孩子遍历，来遍历每一层的头结点；而对单层内的节点 p 可以通过 next 指针遍历，然后进行以下操作：

  • p->left->next = p->right;
  • p->right->next = p->next->left;

代码

class Solution {
public:
    Node* connect(Node* root) {
        Node* cur = root;
        while (cur) {
            for (Node* p = cur; p; p = p->next) {
                if (p->left) p->left->next = p->right;
                if (p->right && p->next) p->right->next = p->next->left;
            }
            cur = cur->left;
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 0117. 填充每个节点的下一个右侧节点指针 II (opens new window)

题目

给定一个二叉树

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
1
2
3
4
5
6

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

解析

相比于 0116. 填充每个节点的下一个右侧节点指针，本题给出的二叉树没有满二叉树的限制，因此可能存在空节点，所以需要增加两个辅助指针，用来维护下一层的头结点和尾结点，其中，头结点用于切换，尾结点用于插入。

代码

class Solution {
public:
    Node* connect(Node* root) {
        Node* cur = root;
        while (cur) {
            Node *head = new Node(), *tail = head;
            for (Node* p = cur; p; p = p->next) {
                if (p->left) tail = tail->next = p->left;
                if (p->right) tail = tail->next = p->right;
            }
            cur = head->next;
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 0156. 上下翻转二叉树 (opens new window)

题目

解析

代码

# 0222. 完全二叉树的节点个数 (opens new window)

题目

解析

代码

# 0255. 验证前序遍历序列二叉搜索树 (opens new window)

题目

解析

代码

# 0314. 二叉树的垂直遍历 (opens new window)

题目

解析

代码

# 0331. 验证二叉树的前序序列化 (opens new window)

题目

解析

代码

# 0333. 最大 BST 子树 (opens new window)

题目

解析

代码

# 0427. 建立四叉树 (opens new window)

题目

解析

代码

# 0545. 二叉树的边界 (opens new window)

题目

解析

代码

# 0558. 四叉树交集 (opens new window)

题目

解析

代码

Last Updated: 2023-01-28 4:31:25

树形结构：基础