C++ solution


  • 0
    0
    class Solution {
    public:
        vector<int> boundaryOfBinaryTree(TreeNode* root) {
            if (!root) return {};
            vector<int> ret {root->val};
            vector<TreeNode*> l, r, b;
            unordered_set<TreeNode*> s {root};
            lb(root->left, l);
            al(root, b);
            rb(root->right, r);
            for (auto n : l) { if (s.count(n)) continue; ret.push_back(n->val); s.insert(n); }
            for (auto n : b) { if (s.count(n)) continue; ret.push_back(n->val); s.insert(n); }
            for (auto n : r) { if (s.count(n)) continue; ret.push_back(n->val); s.insert(n); }
            return ret;
        }
    
        void lb(TreeNode* r, vector<TreeNode*>& l) {
            while (r) {
                l.push_back(r);
                if (r->left) r = r->left; else r = r->right;
            }
        }
    
        void rb(TreeNode* r, vector<TreeNode*>& l) {
            while (r) {
                l.push_back(r);
                if (r->right) r = r->right; else r = r->left;
            }
            reverse(l.begin(), l.end());
        }
    
        void al(TreeNode* r, vector<TreeNode*>& l) {
            if (!r) return;
            if (!r->left && !r->right) l.push_back(r);
            al(r->left, l);
            al(r->right, l);
        }
    };

  • 0
    S

    Good Solution.

    I got the same ideal, but not use unordered_set, so I have to judge whether leafs nodes already exist in left boundary, and whether right boundary already exist in left boundary or leafs. It costs a lot of time to search. But with unordered_set, the search time complexity decrease a lot.


  • 0
    S

    It 's expensive and not necessary to use hash to check whether the node is visited.
    Because there are at most three node may visited twice or more, which are root, left most leaf and right most leaf node.

    Here is the code for reference,

    class Solution {
        TreeNode *_root, *_left, *_right;
        void travel_left(TreeNode *root, vector<int> &left) {
            while (root) {
                left.push_back(root->val);
                _left = root;
                if (root->left) root = root->left;
                else root = root->right;
            }
        }
        void travel_leaves(TreeNode *root, vector<int> &leaves) {
            if (!root) return;
            if (!root->left && !root->right && root != _left && root != _root) {
                leaves.push_back(root->val);
                _right = root;
                return;
            }
            travel_leaves(root->left, leaves);
            travel_leaves(root->right, leaves);
        }
        void travel_right(TreeNode *root, vector<int> &right) {
            while (root) {
                if (root != _right)
                    right.push_back(root->val);
                if (root->right) root = root->right;
                else root = root->left;
            }
        }
    public:
        vector<int> boundaryOfBinaryTree(TreeNode* root) {
            _root = root;
            _left = _right = nullptr;
            vector<int> left, leaves, right, ans;
            if (!root) return ans;
            left.push_back(root->val);
            travel_left(root->left, left);
            travel_leaves(root, leaves);
            travel_right(root->right, right);
            
            ans.insert(ans.end(), left.begin(), left.end());
            ans.insert(ans.end(), leaves.begin(), leaves.end());
            ans.insert(ans.end(), right.rbegin(), right.rend());
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.