Basic binary tree problems

107. Binary Tree Level Order Traversal II

6 min readJul 2, 2020

/**
 * 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;
    }
};

270. Closest Binary Search Tree Value

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

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;
    }
};