Posts tagged as “recursion”

花花酱 LeetCode 563. Binary Tree Tilt

By zxi on March 20, 2018

Problem

https://leetcode.com/problems/binary-tree-tilt/description/

题目大意：返回树的总tilt值。对于一个节点的tilt值定义为左右子树元素和的绝对之差。

Given a binary tree, return the tilt of the whole tree.

The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.

The tilt of the whole tree is defined as the sum of all nodes’ tilt.

Example:

Input: 
         1
       /   \
      2     3
Output: 1
Explanation: 
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1

Note:

The sum of node values in any subtree won’t exceed the range of 32-bit integer.
All the tilt values won’t exceed the range of 32-bit integer.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 17 ms

class Solution {

public:

int findTilt(TreeNode* root) {

int sum;

return findTilt(root, sum);

}

private:

// return the total tilt and sum of the root.

int findTilt(TreeNode* root, int& sum) {

if (root == nullptr) return 0;

int ls = 0;

int rs = 0;

int tl = findTilt(root->left, ls);

int tr = findTilt(root->right, rs);

sum = root->val + ls + rs;

return tl + tr + abs(ls - rs);

}

};

v1-2

// Author: Huahua

// Running time: 17 ms

class Solution {

public:

int findTilt(TreeNode* root) {

return findTiltSum(root).first;

}

private:

pair<int, int> findTiltSum(TreeNode* root) {

if (root == nullptr) return {0, 0};

auto l = findTiltSum(root->left);

auto r = findTiltSum(root->right);

return { l.first + r.first + abs(l.second - r.second),

root->val + l.second + r.second };

}

};

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int findTilt(TreeNode* root) {

ans_ = 0;

sum(root);

return ans_;

}

private:

int ans_;

int sum(TreeNode* root) {

if (root == nullptr) return 0;

int l = sum(root->left);

int r = sum(root->right);

ans_ += abs(l - r);

return root->val + l + r;

}

};

Python3

"""

Author: Huahua

Running time: 112 ms

"""

class Solution:

def findTilt(self, root):

def findTilt(root):

if not root: return 0, 0

tl, sl = findTilt(root.left)

tr, sr = findTilt(root.right)

return tl + tr + abs(sl - sr), root.val + sl + sr

return findTilt(root)[0]

花花酱 LeetCode 572. Subtree of Another Tree

By zxi on March 19, 2018

Problem

题目大意：判断一棵树是不是另外一棵树的子树。

https://leetcode.com/problems/subtree-of-another-tree/description/

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

/ \

4 5

/ \

1 2

Given tree t:

/ \

1 2

Return true, because t has the same structure and node values with a subtree of s.

Example 2:
Given tree s:

/ \

4 5

/ \

1 2

Given tree t:

/ \

1 2

Return false.

Solution: Recursion

Time complexity: O(max(n, m))

Space complexity: O(max(n, m))

C++

// Author: Huahua

// Running time: 29 ms

class Solution {

public:

bool isSubtree(TreeNode* s, TreeNode* t) {

if (t == nullptr) return true;

if (s == nullptr) return false;

if (isSameTree(s, t)) return true;

return isSubtree(s->left, t) || isSubtree(s->right, t);

}

private:

bool isSameTree(TreeNode* s, TreeNode* t) {

if (s == nullptr && t == nullptr) return true;

if (s == nullptr || t == nullptr) return false;

return (s->val == t->val)

&& isSameTree(s->left, t->left)

&& isSameTree(s->right, t->right);

}

};

Problem

https://leetcode.com/problems/add-one-row-to-tree/description/

Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root’s left subtree.

Example 1:

Input: 
A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5   

v = 1

d = 2

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

Example 2:

Input: 
A binary tree as following:
      4
     /   
    2    
   / \   
  3   1    

v = 1

d = 3

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

Note:

The given d is in range [1, maximum depth of the given tree + 1].
The given binary tree has at least one tree node.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 19 ms (beats 90.85%)

class Solution {

public:

TreeNode* addOneRow(TreeNode* root, int v, int d) {

if (root == nullptr) return nullptr;

// Special case.

if (d == 1) {

TreeNode* new_root = new TreeNode(v);

new_root->left = root;

return new_root;

}

if (d == 2) {

TreeNode* l = root->left;

root->left = new TreeNode(v);

root->left->left = l;

TreeNode* r = root->right;

root->right = new TreeNode(v);

root->right->right = r;

} else {

addOneRow(root->left, v, d - 1);

addOneRow(root->right, v, d - 1);

}

return root;

}

};

花花酱 LeetCode 337. House Robber III

By zxi on March 15, 2018

题目大意：给你一棵二叉树，不能同时取两个相邻的节点(parent/child)，问最多能取得的节点的值的和是多少。

Problem:

https://leetcode.com/problems/house-robber-iii/description/

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Maximum amount of money the thief can rob = 4 + 5 = 9.

Idea:

Compare grandparent + max of grandchildren(l.l + l.r + r.l + r.r) vs max of children (l + r)

Solution 1: Recursion w/o memorization

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 1289 ms

class Solution {

public:

int rob(TreeNode* root) {

if (root == nullptr) return 0;

int val = root->val;

int ll = root->left ? rob(root->left->left) : 0;

int lr = root->left ? rob(root->left->right) : 0;

int rl = root->right ? rob(root->right->left) : 0;

int rr = root->right ? rob(root->right->right) : 0;

return max(val + ll + lr + rl + rr, rob(root->left) + rob(root->right));

}

};

Solution 2: Recursion w/ memorization

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

int rob(TreeNode* root) {

if (root == nullptr) return 0;

if (m_.count(root)) return m_[root];

int val = root->val;

int ll = root->left ? rob(root->left->left) : 0;

int lr = root->left ? rob(root->left->right) : 0;

int rl = root->right ? rob(root->right->left) : 0;

int rr = root->right ? rob(root->right->right) : 0;

return m_[root] = max(val + ll + lr + rl + rr, rob(root->left) + rob(root->right));

}

private:

unordered_map<TreeNode*, int> m_;

};

Solution 3: Recursion return children’s value

// Author: Huahua

// Running time: 10 ms (beats 97.57%)

class Solution {

public:

int rob(TreeNode* root) {

int l = 0;

int r = 0;

return rob(root, l, r);

}

private:

// return rob(root) and stores rob(root->left/right) in l/r.

int rob(TreeNode* root, int& l, int& r) {

if (root == nullptr) return 0;

int ll = 0;

int lr = 0;

int rl = 0;

int rr = 0;

l = rob(root->left, ll, lr);

r = rob(root->right, rl, rr);

return max(root->val + ll + lr + rl + rr, l + r);

}

};

Python3

"""

Author: Huahua

Running time: 64 ms (beats 93.18%)

"""

class Solution:

def rob(self, root):

def rob(root):

if not root: return 0, 0, 0

l, ll, lr = rob(root.left)

r, rl, rr = rob(root.right)

return max(root.val + ll + lr + rl + rr, l + r), l, r

return rob(root)[0]

Related Problems:

花花酱 LeetCode 198. House Robber

花花酱 LeetCode 636. Exclusive Time of Functions

By zxi on February 5, 2018

题目大意：给你一些函数的起始/终止时间的日志，让你输出每个函数的总运行时间。假设单核单线程，支持递归函数。

Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.

Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.

A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0.

Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function’s exclusive time. You should return the exclusive time of each function sorted by their function id.

Example 1:

Input:

n = 2

logs =

["0:start:0",

"1:start:2",

"1:end:5",

"0:end:6"]

Output:[3, 4]

Explanation:

Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.

Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.

Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.

So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.

Note:

Input logs will be sorted by timestamp, NOT log id.
Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
Two functions won’t start or end at the same time.
Functions could be called recursively, and will always end.
1 <= n <= 100

Solution: Simulate using stack

// Author: Huahua

// Running time: 35 ms

class Solution {

public:

vector<int> exclusiveTime(int n, vector<string>& logs) {

vector<int> ans(n, 0);

char action[6];

int fid;

int curr;

int prev;

stack<int> s;

for (const string& log : logs) {

sscanf(log.c_str(), "%d:%[a-z]:%d", &fid, action, &curr);

if (action[0] == 's') {

if (!s.empty())

ans[s.top()] += curr - prev;

s.push(fid);

prev = curr;

} else {

ans[s.top()] += curr - prev + 1;

s.pop();

prev = curr + 1;

}

return ans;

}

};

Posts tagged as “recursion”

花花酱 LeetCode 563. Binary Tree Tilt

Problem

Solution: Recursion

花花酱 LeetCode 572. Subtree of Another Tree

Problem

Solution: Recursion

Related Problems

花花酱 LeetCode 623. Add One Row to Tree

Problem

Solution: Recursion

花花酱 LeetCode 337. House Robber III

花花酱 LeetCode 636. Exclusive Time of Functions