Basic binary tree problems

`/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    void helper(vector<vector<int>> &ret, TreeNode* node, int level){        if (node==nullptr)return;        if (ret.size() >=level+1)ret[level].push_back(node->val);        else ret.push_back({node->val});        helper(ret, node->left, level+1);        helper(ret, node->right, level+1);            }    vector<vector<int>> levelOrderBottom(TreeNode* root) {        vector<vector<int>> ret;        helper(ret, root, 0);        reverse(ret.begin(), ret.end());        return ret;    }};`

100. Same Tree

`/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    bool isSameTree(TreeNode* p, TreeNode* q) {        if ((p && !q) ||(!p&&q))return false;        else if(p && q)        {            if (p->val != q->val)return false;            return isSameTree(p->left, q->left) &&  isSameTree(p->right, q->right);        }        else return true;    }};`

236. Lowest Common Ancestor of a Binary Tree

C++

`/** * 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:    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {        if (root ==p || root ==q) return root;        if (!root)return nullptr;        auto left = lowestCommonAncestor(root->left, p, q);        auto right = lowestCommonAncestor(root->right, p, q);        if (left && right)return root;        return left? left: right;            }};`

Python

`# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':        if root in (None, p, q): return root        left, right = (self.lowestCommonAncestor(kid, p, q)                   for kid in (root.left, root.right))        return root if left and right else left or right`

106. Construct Binary Tree from Inorder and Postorder Traversal

Non in place got TLE

`/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {        if (inorder.size()==0)return nullptr;                auto root_val = postorder.back();postorder.pop_back();        TreeNode* node = new TreeNode(root_val);        vector<int> left_inorder, right_inorder;        set<int> left;        bool is_left = true;        for (auto x : inorder)        {            if (x == root_val)             {                is_left = false;                continue;            }            if (is_left)            {                left_inorder.push_back(x);                left.insert(x);            }            else            {                right_inorder.push_back(x);            }        }        vector<int> left_postorder(postorder.begin(), postorder.begin()+left_inorder.size());        vector<int> right_postorder(postorder.begin()+left_inorder.size() , postorder.end());        TreeNode* left_tree = buildTree(left_inorder, left_postorder);        TreeNode* right_tree = buildTree(right_inorder, right_postorder);        node->left = left_tree;        node->right = right_tree;        return node;    }};`

Inplace got AC

`/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    TreeNode* helper(map<int, int>& pos, vector<int>& inorder, vector<int>& postorder, int i, int j, int ii, int jj)    {        TreeNode* node = new TreeNode(postorder[jj]);        if (i == j) return node;        auto idx = pos[postorder[jj]];        if (idx == i )        {            node->left = nullptr;            ii = ii + (idx - i);            auto right = helper(pos, inorder, postorder, i+1, j, ii ,jj-1);            node -> right = right;        }        else if (idx == j)        {            jj = ii + (idx - i - 1);            auto  left = helper(pos, inorder, postorder, i, j-1, ii , jj);            node->left = left;            node->right = nullptr;        }        else        {            auto  new_jj = ii + (idx - i - 1);            auto left = helper(pos, inorder, postorder, i, idx-1, ii , new_jj);            node->left = left;            auto  new_ii = ii + (idx - i);            auto right = helper(pos, inorder, postorder, idx+1, j, new_ii ,jj-1);            node -> right = right;        }        return node;            }    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {        map<int, int> pos;        const int n = inorder.size();        if (n == 0)return nullptr;        for (int i = 0; i < n; ++i)        {            pos[inorder[i]] = i;        }        return helper(pos, inorder, postorder, 0, n-1, 0, n-1);           }};`

987. Vertical Order Traversal of a Binary Tree

`/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; *///typedef pair<int, int> ii;typedef tuple<int, int, int> iii;typedef vector<iii> viii;class Solution {public:    void helper(viii& ret, TreeNode* node, int hlevel, int vlevel)    {        if (!node) return;        ret.emplace_back(vlevel, hlevel, node->val);        helper(ret, node->left, hlevel+1, vlevel - 1);        helper(ret, node->right, hlevel+1, vlevel + 1);    }    vector<vector<int>> verticalTraversal(TreeNode* root) {        viii ret;        helper(ret, root, 0, 0);        sort(ret.begin(), ret.end());        // push back a dummy element at the end to make sure that we can contain all the results during the for loops        ret.emplace_back(10000, 10000, 10000);        vector<vector<int>> fin_ret;        int current_level = get<0>(ret.front());        vector<int> this_ret;        for (auto& [vlevel, hlevel, val] : ret)        {            if (vlevel == current_level) this_ret.push_back(val);            else             {                fin_ret.push_back(this_ret);                this_ret.clear();                current_level = vlevel;                this_ret.push_back(val);            }        }        return fin_ret;    }};`

O(n) solution

`/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    void helper(TreeNode* node, double& target, double& delta, int& ret)    {        if (!node)return;        if (abs(node->val - target) < delta)        {            delta = abs(node->val - target);            ret = node->val;        }        helper(node->left, target, delta, ret);        helper(node->right, target, delta, ret);    }    int closestValue(TreeNode* root, double target) {        double delta = 1e18;        int ret = 0;        helper(root, target, delta, ret);        return ret;    }};`

O(log h) solution

`/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    int closestValue(TreeNode* root, double target) {       int a = root->val;       auto kid = target < a ? root->left : root->right;       if (!kid) return a;       int b = closestValue(kid, target);       return abs(a - target) < abs(b - target) ? a : b;    }};`

437. Path Sum III

For this problem, we need know the parent node of current node. We can simply use the

1

2 3

methods to encode the node index. However, it will get overflow if we only have nodes in one side. In order to solve this problem, we can build a map to recording the parent and child relationships.

`/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    void helper(TreeNode* node, int& i, int& sum, int& ret, vector<unordered_map<int, int>>& m, unordered_map<int, int>& p)    {        if (!node)return;        int parent = p[i];                if (i == 1)        {            m[i][node->val] += 1;        }            else        {           for (auto x: m[parent])           {               m[i][x.first + node->val] += x.second;           }           m[i][node->val] += 1;        }                if (m[i].count(sum))         {            ret+=m[i][sum];        }        int old_i = i;        p[i+1] = old_i;        i++;        helper(node->left, i , sum, ret, m, p);        i++;        p[i] = old_i;        helper(node->right, i , sum, ret, m, p);    }    int pathSum(TreeNode* root, int sum) {        int ret = 0;        vector<unordered_map<int, int>> m(2000);        unordered_map<int, int> p;        p[1] = 0;        int i = 1;        helper(root, i, sum, ret, m, p);        return ret;    }};`

--

--

--

More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Jimmy Shen

Data Scientist/MLE/SWE @takemobi