花花酱 LeetCode 617. Merge Two Binary Trees

By zxi on August 17, 2018

Problem

Given two binary trees and 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 them 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 new tree.

Example 1:

Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

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

Solution: Recursion

Reuse t1/t2

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {

if (t1 == nullptr) return t2;

if (t2 == nullptr) return t1;

auto root = t1;

root->val += t2->val;

root->left = mergeTrees(t1->left, t2->left);

root->right = mergeTrees(t1->right, t2->right);

return root;

}

};

Create a copy

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {

if (t1 == nullptr) return copyTree(t2);

if (t2 == nullptr) return copyTree(t1);

TreeNode* root = new TreeNode(t1->val + t2->val);

root->left = mergeTrees(t1->left, t2->left);

root->right = mergeTrees(t1->right, t2->right);

return root;

}

private:

TreeNode* copyTree(TreeNode* root) {

if (root == nullptr) return nullptr;

TreeNode* r = new TreeNode(root->val);

r->left = copyTree(root->left);

r->right = copyTree(root->right);

return r;

}

};

花花酱 LeetCode 655. Print Binary Tree

By zxi on August 17, 2018

Problem

Print a binary tree in an m*n 2D string array following these rules:

The row number m should be equal to the height of the given binary tree.
The column number n should always be an odd number.
The root node’s value (in string format) should be put in the exactly middle of the first row it can be put. The column and the row where the root node belongs will separate the rest space into two parts (left-bottom part and right-bottom part). You should print the left subtree in the left-bottom part and print the right subtree in the right-bottom part. The left-bottom part and the right-bottom part should have the same size. Even if one subtree is none while the other is not, you don’t need to print anything for the none subtree but still need to leave the space as large as that for the other subtree. However, if two subtrees are none, then you don’t need to leave space for both of them.
Each unused space should contain an empty string "".
Print the subtrees following the same rules.

Example 1:

Input:
     1
    /
   2
Output:
[["", "1", ""],
 ["2", "", ""]]

Example 2:

Input:
     1
    / \
   2   3
    \
     4
Output:
[["", "", "", "1", "", "", ""],
 ["", "2", "", "", "", "3", ""],
 ["", "", "4", "", "", "", ""]]

Example 3:

Input:
      1
     / \
    2   5
   / 
  3 
 / 
4 
Output:

[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
 ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
 ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
 ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]

Note: The height of binary tree is in the range of [1, 10].

Solution: Recursion

Compute the layers h of the tree.

shape of the output matrix: h * w (w = 2^h – 1)

pre-order to fill the output matrix

first layer’s root: y1 = 0, x1 = (l1 + r1) / 2 = (0 + w – 1) / 2 (center)

first layer’s left child (2nd layer): y2 = 1, x2 = (l2 + r2) = (l1 + (x1 – 1)) / 2 (center of the left half)

first layer’s right child(2nd layer): y1 = 2, x2 = (l2′ + r2′) = ((x1+1) + r1) / 2 (center of the right half)

…

Time complexity: O(m*n)

Space complexity: O(m*n)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

vector<vector<string>> printTree(TreeNode* root) {

int h = getHeight(root);

int w = (1 << h) - 1; // 2 ^ h - 1

vector<vector<string>> ans(h, vector<string>(w, ""));

fill(root, ans, 0, 0, w - 1);

return ans;

}

private:

int getHeight(TreeNode* root) {

if (!root) return 0;

return max(getHeight(root->left), getHeight(root->right)) + 1;

}

void fill(TreeNode* root, vector<vector<string>>& ans, int h, int l, int r){

if (!root) return;

int mid = (l + r) / 2;

ans[h][mid] = std::to_string(root->val);

fill(root->left, ans, h + 1, l, mid - 1);

fill(root->right, ans, h + 1, mid + 1, r);

}

};

Python3

"""

Author: Huahua

Running time: 44 ms

"""

class Solution:

def printTree(self, root):

def height(root):

if not root: return 0

return max(height(root.left), height(root.right)) + 1

def fill(root, h, l, r):

if not root: return

mid = (l + r) // 2

m[h][mid] = str(root.val)

if root.left: fill(root.left, h + 1, l, mid - 1)

if root.right: fill(root.right, h + 1, mid + 1, r)

h = height(root)

w = 2**h - 1

m = [[""] * w for _ in range(h)]

fill(root, 0, 0, w - 1)

return m

花花酱 LeetCode 404. Sum of Left Leaves

By zxi on August 16, 2018

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int sumOfLeftLeaves(TreeNode* root) {

if (!root) return 0;

if (root->left && !root->left->left && !root->left->right)

return root->left->val + sumOfLeftLeaves(root->right);

return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);

}

};

Iterative

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int sumOfLeftLeaves(TreeNode* root) {

if (!root) return 0;

queue<TreeNode*> q;

q.push(root);

int sum = 0;

while (!q.empty()) {

TreeNode* n = q.front();

q.pop();

TreeNode* l = n->left;

if (l) {

if (!l->left && !l->right)

sum += l->val;

else

q.push(l);

}

if (n->right) q.push(n->right);

}

return sum;

}

};

花花酱 LeetCode 101. Symmetric Tree

By zxi on July 26, 2018

Problem

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

class Solution {

public:

bool isSymmetric(TreeNode* root) {

return isMirror(root, root);

}

private:

bool isMirror(TreeNode* root1, TreeNode* root2) {

if (!root1 && !root2) return true;

if (!root1 || !root2) return false;

return root1->val == root2->val

&& isMirror(root1->right, root2->left)

&& isMirror(root1->left, root2->right);

}

};

Python

"""

Author: Huahua

Running time: 48 ms

"""

class Solution:

def isSymmetric(self, root):

def isMirror(root1, root2):

if not root1 and not root2: return True

if not root1 or not root2: return False

return root1.val == root2.val \

and isMirror(root1.left, root2.right) \

and isMirror(root2.left, root1.right)

return isMirror(root, root)

Problem

Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Note:

Both of the given trees will have between 1 and 100 nodes.

Solution: Recursion

Time complexity: O(n1 + n2)

Space complexity: O(n1 + n2)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

bool leafSimilar(TreeNode* root1, TreeNode* root2) {

vector<int> leafs1;

vector<int> leafs2;

getLeafs(root1, leafs1);

getLeafs(root2, leafs2);

return leafs1 == leafs2;

}

private:

void getLeafs(TreeNode* root, vector<int>& leafs) {

if (root == nullptr) return;

if (root->left == nullptr && root->right == nullptr)

leafs.push_back(root->val);

getLeafs(root->left, leafs);

getLeafs(root->right, leafs);

}

};

Python

"""

Author: Huahua

Running time: 24 ms

"""

class Solution(object):

def leafSimilar(self, root1, root2):

def getLeafs(root):

if not root: return []

if not root.left and not root.right: return [root.val]

return getLeafs(root.left) + getLeafs(root.right)

return getLeafs(root1) == getLeafs(root2)

Posts published in “Tree”

花花酱 LeetCode 617. Merge Two Binary Trees

Problem

Solution: Recursion

花花酱 LeetCode 655. Print Binary Tree

Problem

Solution: Recursion

C++

Python3

花花酱 LeetCode 404. Sum of Left Leaves

Solution: Recursion

花花酱 LeetCode 101. Symmetric Tree

Problem

Solution: Recursion

C++

Python

Related Problems

花花酱 LeetCode 872. Leaf-Similar Trees

Problem

Solution: Recursion