通关算法题之 ⌈二叉树⌋ 下_matlab二叉搜索树

填充每个节点的下一个右侧节点指针

116、填充每个节点的下一个右侧节点指针

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

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

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

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

示例：

输入：root = [1,2,3,4,5,6,7]
输出：[1,##,2,3,##,4,5,6,7,##]
1
2

这道题若使用常规的遍历二叉树的话，只能将一个节点的左子树指向右子树，不同节点的子树之间无法建立联系，所以要改变遍历的方式。传统的 traverse 函数是遍历二叉树的所有节点，但现在我们想遍历的其实是两个相邻节点之间的「空隙」，所以可以在二叉树的基础上进行抽象，把图中的每一个方框看做一个节点：

解法一：递归遍历二叉树

这样，一棵二叉树被抽象成了一棵三叉树，三叉树上的每个节点就是原先二叉树的两个相邻节点。

现在，我们只要实现一个 traverse 函数来遍历这棵三叉树，每个「三叉树节点」需要做的事就是把自己内部的两个二叉树节点穿起来。这样，traverse 函数遍历整棵「三叉树」，将所有相邻节的二叉树节点都连接起来，也就避免了我们之前出现的问题，把这道题完美解决。

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return root;
        traverse(root->left, root->right);
        return root;
    }
    // 三叉树遍历框架
    void traverse(Node* node1, Node* node2){
        if(!node1 || !node2){
            return;
        }
        node1->next = node2;
        traverse(node1->left, node1->right);
        traverse(node2->left, node2->right);
        traverse(node1->right, node2->left);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解法二：层序遍历

在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点。

核心代码逻辑为：

• 遍历到每一层的第一个节点时，用pre记录该节点，然后节点出队，node记录pre；

• 向后每遍历一个节点，用node记录该节点，然后节点出队，pre指向node，pre指针向后移动一位；

• 该层最后一个节点指向nullptr；

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            Node* pre;
            Node* node;
            for (int i = 0; i < size; i++) {
                if (i == 0) {
                    pre = que.front(); // 取出一层的头结点
                    que.pop();
                    node = pre;
                } else {
                    node = que.front();
                    que.pop();
                    pre->next = node; // 本层前一个节点next指向本节点
                    pre = pre->next;
                }
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            pre->next = NULL; // 本层最后一个节点指向NULL
        }
        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

二刷：

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if(root) que.push(root);
        while(!que.empty()){
            int size = que.size();
            Node* pre;
            for(int i = 0; i < size; i++){
                Node* node = que.front();
                que.pop();
                if(i == 0){
                    pre = node;
                }else{
                    pre->next = node;
                    pre = node;
                }
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            pre->next = NULL;
        }
        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

二叉树序列化

297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
1
2

使用拼接字符串的方式把二叉树序列化。

class Codec {
public:

    // 序列化
    string serialize(TreeNode* root) {
        if(!root) return "##";
        return to_string(root->val) + " " + serialize(root->left) + " " + serialize(root->right);
    }

     TreeNode* build(istringstream& iss){
        string tmp;
        iss>>tmp;
        if(tmp == "##") return NULL;
        TreeNode* root = new TreeNode(stoi(tmp));
        root->left = build(iss);
        root->right = build(iss);
        return root;
    }
    // 反序列化
    TreeNode* deserialize(string data) {
        istringstream iss(data);
        return build(iss);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

652、寻找重复的子树

给定一棵二叉树 root，返回所有重复的子树。

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

如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

示例：

输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]
1
2

如何知道以某个节点为根的子树是不是重复的，是否应该加入结果列表中，需要知道什么信息呢？

你需要知道以下两点：

1、以我为根的这棵二叉树（子树）长啥样？——后序遍历

2、以其他节点为根的子树都长啥样？——利用哈希表存起来做比较

现在，明确了要用后序遍历，那应该怎么描述一棵二叉树的模样呢？二叉树的前序/中序/后序遍历结果可以描述二叉树的结构。所以，可以通过拼接字符串的方式把二叉树序列化。

class Solution {
public:
    unordered_map<string, int> map;
    vector<TreeNode*> res;
    
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
		traverse(root);
		return res;
    }
    //定义：输入一个节点，将以该节点为根节点的二叉树序列化，返回序列化后的字符串
    string traverse(TreeNode* root){
		if(!root) return "##";
       	string left = traverse(root->left);
        string right = traverse(root->right);
        // 后序位置获取二叉树序列化后的字符串
        string str = left + "," + right + "," + to_string(root->val);
        if(map[str] == 1){
            res.push_back(root);
        }
        map[str]++;
        return str;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

构造二叉树