C++ calculate index of each node


  • 0
    B
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<vector<string>> printTree(TreeNode* root) {
            int h = getHeight(root);
            vector<vector<string>>ans(h, vector<string>((int)pow(2,h)-1, ""));
            if(h == 0) return ans;
            getValue(root, ans, (int)pow(2,h-1)-1, 1, h);
            return ans;
        }
        
        int getHeight(TreeNode* root)
        {
            if(!root) return 0;
            return 1 + max(getHeight(root->left), getHeight(root->right));
        }
        
        void getValue(TreeNode* root, vector<vector<string>> & ans, int idx, int level, int height)
        {
            if(!root) return;
            ans[level-1][idx] = to_string(root -> val);
            if(level == height) return;
            getValue(root->left, ans, idx-(int)pow(2, height-level-1), level+1, height);
            getValue(root->right, ans, idx+(int)pow(2, height-level-1), level+1, height);
        }
    };

Log in to reply
 

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