Jonathan's Coding Interview 👨‍💻

    106 - Construct Binary Tree From Inorder And Postorder Traversal & 654 - Maximum Binary Tree & 617 - Merge Two Binary Trees

    #medium

    Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

    Example 1:

    Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
    Output: [3,9,20,null,null,15,7]

    Example 2:
    Input: inorder = [-1], postorder = [-1]
    Output: [-1]

    /**
 * 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 * traversal( vector<int> & inorder, vector<int> & postorder ) {
        // 後序遍歷數組最後一個元素，就是當前的中間節點
        if ( postorder.size() == 0 ) return NULL;
        int rootValue = postorder[postorder.size()-1];
        TreeNode * root  = new TreeNode(rootValue);

        // 葉子節點
        if ( postorder.size() == 1 ) return root;

        // 找到中序遍歷的切割點
        int delimiterIndex;
        for ( delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++ ) {
            if ( inorder[delimiterIndex] == rootValue ) break;
        }

        // 切割中序數組 (左開右閉，右邊為被切開的值)
        vector<int> leftInorder( inorder.begin(), inorder.begin() + delimiterIndex );
        vector<int> rightInorder( inorder.begin() + delimiterIndex + 1 , inorder.end() );
        // postorder 捨棄末尾元素
        postorder.resize(postorder.size() - 1);

        // 切割後序數組
        // 依然左閉右開，注意這裡使用了左中序數組大小作為切割點
        // [0, leftInorder.size)
        vector<int> leftPostorder( postorder.begin(), postorder.begin() + leftInorder.size() );
        vector<int> rightPostorder( postorder.begin() + leftInorder.size(), postorder.end() );

        root -> left = traversal( leftInorder, leftPostorder );
        root -> right = traversal( rightInorder, rightPostorder );
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return traversal( inorder, postorder );
    }   
};

    654 - Maximum Binary Tree

    #medium

    You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

    1. Create a root node whose value is the maximum value in nums.
    2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
    3. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

    Return the maximum binary tree built from nums.

    Example 1:

    Input: nums = [3,2,1,6,0,5]
    Output: [6,3,5,null,2,0,null,null,1]
    Explanation: The recursive calls are as follow:

    • The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
      • The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
        • Empty array, so no child.
        • The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
          • Empty array, so no child.
          • Only one element, so child is a node with value 1.
      • The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
        • Only one element, so child is a node with value 0.
        • Empty array, so no child.

    Example 2:

    Input: nums = [3,2,1]
    Output: [3,null,2,null,1]

    class Solution {
public:
    TreeNode * traversal( vector<int> & nums ) {
        if ( nums.size() == 0 ) return NULL;
        auto it = max_element(nums.begin(), nums.end());
        int index = distance( nums.begin(), it );
        TreeNode * root = new TreeNode( nums[index] );
        if ( nums.size() == 1 ) return root;

        vector<int> left_nums( nums.begin(), nums.begin() + index );
        vector<int> right_nums( nums.begin() + index + 1, nums.end() );

				// 數組中左邊最大，不往左邊建樹
        if ( index > 0 ) root -> left = traversal( left_nums ); 

				// 樹組中右邊最大，不往右邊建樹
        if ( nums.size() != index + 1 ) root -> right = traversal( right_nums );
        return root;
    }



    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return traversal( nums );
    }

};

    617 - Merge Two Binary Trees

    #easy

    You are given two binary trees root1 and root2.

    Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

    Return the merged tree.

    Note: The merging process must start from the root nodes of both trees.

    Example 1:

    Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
    Output: [3,4,5,5,4,null,7]

    Example 2:
    Input: root1 = [1], root2 = [1,2]
    Output: [2,2]

    /**
 * 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* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if ( root1 == NULL ) return root2;
        if ( root2 == NULL ) return root1;
        if ( root1 != NULL && root2 != NULL ) {
            root1 -> val += root2 -> val;
        }

        root1 -> left = mergeTrees( root1 -> left, root2 -> left );
        root1 -> right = mergeTrees( root1 -> right, root2 -> right );
        return root1;
    }
};