[545. Boundary of Binary Tree] C++ AC


  • 0

    My method is straightforward, find out the left bound , leaf nodes and right bound. Any suggestion is appreciated.

    class Solution {
    public:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        //consider 3 cases:[1], [1,2], [1, null, 2]
        if(root == nullptr) return {};
        else if(!root->left && !root->right) return {root->val};
        vector<int> res;
        
        //left bound
        res.push_back(root->val);
        findBound(root->left, res, 0);
        if(res.size() > 1) res.pop_back();
        
        //leaves bound
        findLeaves(root, res);
        if(res.size() > 1 && root->right) res.pop_back();
    
        //right bound
        int pos = res.size();
        findBound(root->right, res, 1);
        reverse(res.begin() + pos, res.end());
        
        return res;
    }
    void findBound(TreeNode* root, vector<int>& res, int dir){
        if(dir == 0){
            while(root){
                res.push_back(root->val);
                if(root->left){
                    root = root->left;
                }else if(root->right){
                    root = root->right;
                }else{break;}
            }
        }else{//(dir == 1)
            while(root){
                res.push_back(root->val);
                if(root->right){
                    root = root->right;
                }else if(root->left){
                    root = root->left;
                }else{break;}
            }
        }
    }
    
    void findLeaves(TreeNode* root, vector<int>& res){
        if(!root) return;
        if(!root->left && !root->right){
            res.push_back(root->val);
        }else{
            findLeaves(root->left, res);
            findLeaves(root->right, res);
        }
    }
    };

Log in to reply
 

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