Find The Boundary Of Tree

发表于 | 分类于

Find The Boundary Of Tree(找到树的边界节点)

题目描述：

来自leetcode的contest。具体的题目描述可以在这里找到。

解题思路：

本题主要的难点有：怎么找到左侧边界；怎么找到右侧边界；怎么找到下边界；以及如何将边界连接已经右侧边界的逆序。 根据代码解释一下思路；首先判断根节点是否为空决定是否返回空的vector；其次定义用于保存边界的vector并将根节点的值导入；定义用于保存遍历过程节点的集合，将根节点导入；分别定义vector用于保存左侧边界、右侧边界和下边界；根据遍历函数得到的左右下边界，遍历其中的节点找到不重复的节点连接即为整颗树的边界。

代码如下：

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
class Solution {
public:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        if (!root)
            return {}; // 返回空边界
        vector<int> res = {root->val};//导入根值到边界结果
        unordered_set<TreeNode*> hash = {root};//导入根到遍历节点集合
        
        vector<TreeNode*> left;
        vector<TreeNode*> right;
        vector<TreeNode*> leaf;// 定义三个边界的vector
        
        leftBoundary(root->left, left);
        leafNode(root, leaf);
        rightBoundary(root->right, right);
        // 通过遍历函数找到各自边界的集合，其中集合可能存在重合
        
        for (auto l : left){if (hash.count(l)) continue; res.push_back(l->val); hash.insert(l);}
        //连接左侧边界
        for (auto m : leaf){if (hash.count(m)) continue; res.push_back(m->val); hash.insert(m);}
        //连接下侧边界
        for (auto r: right){if (hash.count(r)) continue; res.push_back(r->val); hash.insert(r);}
        // 连接右侧边界
        return res;
    }
    void leftBoundary(TreeNode* node, vector<TreeNode*>& left){
        while(node){
            left.push_back(node);
            if (node->left) node = node->left;
            else node = node->right;
            // 找到最左侧的边界；不断向左侧遍历，为空就向右侧遍历知道为空
        }
    }
    void leafNode(TreeNode* root, vector<TreeNode*>&leaf){
        if (!root) return;
        if (root->left == NULL && root->right == NULL) leaf.push_back(root);
        else
        {
            leafNode(root->left, leaf);
            leafNode(root->right, leaf);
        }
        //找到所有叶节点的集合即为下边界集合；先判断是否是空节点；然后判断是否是叶节点；然后递归左侧和右侧节点。
    }
    void rightBoundary(TreeNode* node, vector<TreeNode*>& right){
        while(node){
            right.push_back(node);
            if (node->right) node = node->right;
            else node = node->left;
        }//找到右侧边界；同左侧；需要注意的是需要将结果逆序。
        reverse(right.begin(), right.end());
    }
};