Posts tagged as “recursion”

花花酱 LeetCode 64. Minimum Path Sum

By zxi on November 27, 2017

Problem:

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

[[1,3,1],

[1,5,1],

[4,2,1]]

Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

Idea:

Solution 1:

C++ / Recursion with memoization

Time complexity: O(mn)

Space complexity: O(mn)

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int minPathSum(vector<vector<int>>& grid) {

int m = grid.size();

if (m == 0) return 0;

int n = grid[0].size();

s_ = vector<vector<int>>(m, vector<int>(n, 0));

return minPathSum(grid, n - 1, m - 1, n, m);

}

private:

long minPathSum(const vector<vector<int>>& grid,

int x, int y, int n, int m) {

if (x == 0 && y == 0) return grid[y][x];

if (x < 0 || y < 0) return INT_MAX;

if (s_[y][x] > 0) return s_[y][x];

int ans = grid[y][x] + min(minPathSum(grid, x - 1, y, n, m),

minPathSum(grid, x, y - 1, n, m));

return s_[y][x] = ans;

}

vector<vector<int>> s_;

};

Solution 2:

C++ / DP

Time complexity: O(mn)

Space complexity: O(1)

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int minPathSum(vector<vector<int>>& grid) {

int m = grid.size();

if (m == 0) return 0;

int n = grid[0].size();

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

if (i == 0 && j == 0) continue;

if (i == 0)

grid[i][j] += grid[i][j - 1];

else if (j == 0)

grid[i][j] += grid[i - 1][j];

else

grid[i][j] += min(grid[i][j - 1], grid[i - 1][j]);

}

return grid[m - 1][n - 1];

}

};

Related Problems:

[解题报告] LeetCode 113. Path Sum II

花花酱 LeetCode 113. Path Sum II

By zxi on November 27, 2017

Problem:

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

/ \

4 8

/ / \

11 13 4

/ \ / \

7 2 5 1

return

[

[5,4,11,2],

[5,8,4,5]

]

Idea:

Recursion

Solution:

C++

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

vector<vector<int>> pathSum(TreeNode* root, int sum) {

vector<vector<int>> ans;

vector<int> curr;

pathSum(root, sum, curr, ans);

return ans;

}

private:

void pathSum(TreeNode* root, int sum, vector<int>& curr, vector<vector<int>>& ans) {

if(root==nullptr) return;

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

if(root->val == sum) {

ans.push_back(curr);

ans.back().push_back(root->val);

}

return;

}

curr.push_back(root->val);

int new_sum = sum - root->val;

pathSum(root->left, new_sum, curr, ans);

pathSum(root->right, new_sum, curr, ans);

curr.pop_back();

}

};

Related Problems:

花花酱 LeetCode 543. Diameter of Binary Tree

By zxi on October 7, 2017

Problem:

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

/ \

2 3

/ \

4 5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Idea:

Recursion

Solution1:

C++

class Solution {

public:

int diameterOfBinaryTree(TreeNode* root) {

ans_ = 0;

LP(root);

return ans_;

}

private:

int ans_;

int LP(TreeNode* root) {

if (!root) return -1;

int l = LP(root->left) + 1;

int r = LP(root->right) + 1;

ans_ = max(ans_, l + r);

return max(l, r);

}

};

Solution 2: passed 101/106 TLE

C++ / Floyd-Warshall

// Author: Huahua

// State: 101/106 passed TLE

class Solution {

public:

int diameterOfBinaryTree(TreeNode* root) {

if (!root) return 0;

edges_.clear();

int n = 0;

buildGraph(root, n, -1);

vector<vector<int>> d(n, vector<int>(n, n));

for (int i = 0; i < n; ++i) d[i][i] = 0;

for (const auto& pair : edges_)

d[pair.first][pair.second] = 1;

for (int k = 0; k < n; ++k)

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j)

d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

int ans = INT_MIN;

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j) {

if (d[i][j] == n) continue;

ans = max(ans, d[i][j]);

}

return ans;

}

private:

void buildGraph(TreeNode* node, int& id, int pid) {

if (!node) return;

int node_id = id++;

if (pid >= 0) {

edges_.emplace_back(node_id, pid);

edges_.emplace_back(pid, node_id);

}

buildGraph(node->left, id, node_id);

buildGraph(node->right, id, node_id);

}

vector<pair<int,int>> edges_;

};

Solution 3:

Simulate recursion with a stack. We also need to track the return value of each node.

Python

"""

Author: Huahua

Runtime: 82 ms

"""

class Solution:

def diameterOfBinaryTree(self, root):

if not root: return 0

d = {None: -1}

s = [root]

ans = 0

while s:

node = s[-1]

if node.left in d and node.right in d:

s.pop()

l = d[node.left] + 1

r = d[node.right] + 1

ans = max(ans, l + r)

d[node] = max(l, r)

else:

if node.left: s.append(node.left)

if node.right: s.append(node.right)

return ans

C++

// Author: Huahua

// Runtime: 15 ms

class Solution {

public:

int diameterOfBinaryTree(TreeNode* root) {

if (!root) return 0;

int ans = 0;

unordered_map<TreeNode*, int> d{{nullptr, -1}};

stack<TreeNode*> s;

s.push(root);

while (!s.empty()) {

TreeNode* node = s.top();

if (d.count(node->left) && d.count(node->right)) {

int l = d[node->left] + 1;

int r = d[node->right] + 1;

ans = max(ans, l + r);

d[node] = max(l, r);

// children's results will never be used again, safe to delete here.

if (node->left) d.erase(node->left);

if (node->right) d.erase(node->right);

s.pop();

} else {

if (node->left) s.push(node->left);

if (node->right) s.push(node->right);

}

return ans;

}

};

Related Problems:

花花酱 LeetCode 687. Longest Univalue Path

By zxi on October 1, 2017

题目大意：给你一棵二叉树，返回一条最长的路径，要求路径上所有的节点值都相同。

https://leetcode.com/problems/longest-univalue-path/description/

Problem:

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

Note: The length of path between two nodes is represented by the number of edges between them.

Example 1:

Input:

Output:

Example 2:

Input:

Output:

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

Idea:

DFS

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Runtime: 69 ms

class Solution {

public:

int longestUnivaluePath(TreeNode* root) {

if (root == nullptr) return 0;

int ans = 0;

univaluePath(root, &ans);

return ans;

}

private:

int univaluePath(TreeNode* root, int* ans) {

if (root == nullptr) return 0;

int l = univaluePath(root->left, ans);

int r = univaluePath(root->right, ans);

int pl = 0;

int pr = 0;

if (root->left && root->val == root->left->val) pl = l + 1;

if (root->right && root->val == root->right->val) pr = r + 1;

*ans = max(*ans, pl + pr);

return max(pl, pr);

}

};

Java

// Author: Huahua

// Runtime: 12 ms

class Solution {

private int ans;

public int longestUnivaluePath(TreeNode root) {

if (root == null) return 0;

this.ans = 0;

univaluePath(root);

return this.ans;

}

private int univaluePath(TreeNode root) {

if (root == null) return 0;

int l = univaluePath(root.left);

int r = univaluePath(root.right);

int pl = 0;

int pr = 0;

if (root.left != null && root.val == root.left.val) pl = l + 1;

if (root.right != null && root.val == root.right.val) pr = r + 1;

this.ans = Math.max(this.ans, pl + pr);

return Math.max(pl, pr);

}

Python3

"""

Author: Huahua

Runtime: 899 ms

"""

class Solution:

def longestUnivaluePath(self, root):

self.ans = 0

self._univaluePath(root)

return self.ans

def _univaluePath(self, root):

if root is None: return 0

l = self._univaluePath(root.left) if root.left is not None else -1

r = self._univaluePath(root.right) if root.right is not None else -1

pl = l + 1 if l >= 0 and root.val == root.left.val else 0

pr = r + 1 if r >= 0 and root.val == root.right.val else 0

self.ans = max(self.ans, pl + pr)

return max(pl, pr)

Posts tagged as “recursion”

花花酱 LeetCode 64. Minimum Path Sum

花花酱 LeetCode 113. Path Sum II

花花酱 LeetCode 543. Diameter of Binary Tree

花花酱 LeetCode 687. Longest Univalue Path

Solution: Recursion

C++

Java

Python3

Related Problems

花花酱 LeetCode 669. Trim a Binary Search Tree