Posts tagged as “recursion”

花花酱 LeetCode 129. Sum Root to Leaf Numbers

By zxi on October 9, 2019

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Solution: Recursion

Time complexity: O(n)
Space complexity: O(h)

C++

// Author: Huahua

class Solution {

public:

int sumNumbers(TreeNode* root) {

int ans = 0;

function<void(TreeNode*, int)> traverse = [&](TreeNode* t, int num) {

if (!t) return;

num = num * 10 + t->val;

if (t->left || t->right) {

traverse(t->left, num);

traverse(t->right, num);

} else {

ans += num;

}

};

traverse(root, 0);

return ans;

}

};

花花酱 LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

By zxi on October 3, 2019

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

Solution: Recursion

Similar to LC 105

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {

unordered_map<int, int> pos;

for (int i = 0; i < inorder.size(); i++)

pos[inorder[i]] = i;

function<TreeNode*(int, int, int, int)> buildTree = [&](int is, int ie, int ps, int pe) {

if (ps > pe) return (TreeNode*)nullptr;

int im = pos[postorder[pe]];

int pm = ps + (im - is) - 1;

auto root = new TreeNode(postorder[pe]);

root->left = buildTree(is, im - 1, ps, pm);

root->right = buildTree(im + 1, ie, pm + 1, pe - 1);

return root;

};

return buildTree(0, inorder.size() - 1, 0, postorder.size() - 1);

}

};

花花酱 LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

By zxi on October 3, 2019

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

Solution: Recursion

Preprocessing: use a hashtable to store the index of element in preorder array.

For an element in inorder array, find the pos of it in preorder array in O(1), anything to the left will be the leftchild and anything to the right will be the right child.

e.g.
buildTree([9, 3, 15, 20, 7], [3, 9, 20, 15, 7]):
root = TreeNode(9) # inorder[0] = 9
root.left = buildTree([3], [3])
root.right = buildTree([15, 20, 7], [20, 15, 7])
return root

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {

unordered_map<int, int> pos;

for (int i = 0; i < inorder.size(); i++)

pos[inorder[i]] = i;

function<TreeNode*(int, int, int, int)> buildTree = [&](int is, int ie, int ps, int pe) {

if (ps > pe) return (TreeNode*)nullptr;

int im = pos[preorder[ps]];

int pm = ps + (im - is);

auto root = new TreeNode(preorder[ps]);

root->left = buildTree(is, im - 1, ps + 1, pm);

root->right = buildTree(im + 1, ie, pm + 1, pe);

return root;

};

return buildTree(0, inorder.size() - 1, 0, preorder.size() - 1);

}

};

花花酱 LeetCode 116. Populating Next Right Pointers in Each Node

By zxi on August 22, 2019

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {

int val;

Node *left;

Node *right;

Node *next;

}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example:

Input: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

Output: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

Note:

You may only use constant extra space.
Recursive approach is fine, implicit stack space does not count as extra space for this problem.

Solution: Recursion

Do a preorder traversal:
1. return if self is empty or leaf
2. self.left->next = self.right
3. if self.next: self.right.next = self.next.left

Time complexity: O(n)
Space complexity: O(log(n)) since it’s a perfect tree

C++

// Author: Huahua

class Solution {

public:

Node* connect(Node* root) {

if (!root || !root->left) return root;

root->left->next = root->right;

if (root->next)

root->right->next = root->next->left;

connect(root->left);

connect(root->right);

return root;

}

};

花花酱 LeetCode 1110. Delete Nodes And Return Forest

By zxi on August 8, 2019

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

Example 1:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Constraints:

The number of nodes in the given tree is at most 1000.
Each node has a distinct value between 1 and 1000.
to_delete.length <= 1000
to_delete contains distinct values between 1 and 1000.

Solution: Recursion / Post-order traversal

Recursively delete nodes on left subtree and right subtree and return the trimmed tree.
if the current node needs to be deleted, then its non-null children will be added to output array.

Time complexity: O(n)
Space complexity: O(|d| + h)

C++

// Author: Huahua

class Solution {

public:

vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {

vector<TreeNode*> ans;

unordered_set<int> s{begin(to_delete), end(to_delete)};

function<TreeNode*(TreeNode*)> del = [&](TreeNode* n) -> TreeNode* {

if (!n) return nullptr;

if (n->left) n->left = del(n->left);

if (n->right) n->right = del(n->right);

if (!s.count(n->val)) return n;

if (n->left) ans.push_back(n->left);

if (n->right) ans.push_back(n->right);

return nullptr;

};

TreeNode* r = del(root);

if (r) ans.push_back(r);

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:

ans = []

ds = set(to_delete)

def process(n):

if not n: return None

n.left, n.right = process(n.left), process(n.right)

if n.val not in ds: return n

if n.left: ans.append(n.left)

if n.right: ans.append(n.right)

return None

root = process(root)

if root: ans.append(root)

return ans

Posts tagged as “recursion”

花花酱 LeetCode 129. Sum Root to Leaf Numbers

Solution: Recursion

C++

花花酱 LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

Solution: Recursion

C++

Related Problems

花花酱 LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

Solution: Recursion

C++

Related Problems

花花酱 LeetCode 116. Populating Next Right Pointers in Each Node

Solution: Recursion

C++

花花酱 LeetCode 1110. Delete Nodes And Return Forest

Solution: Recursion / Post-order traversal

C++

Python3