花花酱 LeetCode 606. Construct String from Binary Tree

By zxi on August 22, 2018

Problem

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     

Output: "1(2(4))(3)"

Explanation: Originallay it needs to be "1(2(4)())(3()())", 
but you need to omit all the unnecessary empty parenthesis pairs. 
And it will be "1(2(4))(3)".

Example 2:

Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 

Output: "1(2()(4))(3)"

Explanation: Almost the same as the first example, 
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

Solution: Recursion

Time complexity: O(n^2)

space complexity: O(n^2)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

string tree2str(TreeNode* t) {

if (!t) return "";

const string s = std::to_string(t->val);

// case 0: s

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

return s;

// case 1: s(l)

if (!t->right)

return s + "(" + tree2str(t->left) + ")";

// general: s(l)(r)

return s + "(" + tree2str(t->left) + ")" + "(" + tree2str(t->right) + ")";

}

};

花花酱 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)

Posts tagged as “tree”

花花酱 LeetCode 606. Construct String from Binary Tree

Problem

Solution: Recursion

花花酱 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