花花酱 LeetCode 501. Find Mode in Binary Search Tree

By zxi on July 19, 2018

Problem

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

Solution1: Recursion w/ extra space

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

vector<int> findMode(TreeNode* root) {

inorder(root);

return ans_;

}

private:

int val_ = 0;

int count_ = 0;

int max_count_ = 0;

vector<int> ans_;

void inorder(TreeNode* root) {

if (root == nullptr) return;

inorder(root->left);

visit(root->val);

inorder(root->right);

}

void visit(int val) {

if (count_ > 0 && val == val_) {

++count_;

} else {

val_ = val;

count_ = 1;

}

if (count_ > max_count_) {

max_count_ = count_;

ans_.clear();

}

if (count_ == max_count_)

ans_.push_back(val);

}

};

Solution2: Recursion w/o extra space

Two passes. First pass to find the count of the mode, second pass to collect all the modes.

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

vector<int> findMode(TreeNode* root) {

inorder(root);

mode_count_ = max_count_;

count_ = 0;

inorder(root);

return ans_;

}

private:

int val_ = 0;

int count_ = 0;

int mode_count_ = INT_MAX;

int max_count_ = 0;

vector<int> ans_;

void inorder(TreeNode* root) {

if (root == nullptr) return;

inorder(root->left);

visit(root->val);

inorder(root->right);

}

void visit(int val) {

if (count_ > 0 && val == val_) {

++count_;

} else {

val_ = val;

count_ = 1;

}

if (count_ > max_count_)

max_count_ = count_;

if (count_ == mode_count_)

ans_.push_back(val);

}

};

花花酱 LeetCode 429. N-ary Tree Level Order Traversal

By zxi on July 14, 2018

Problem

Given an n-ary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example, given a 3-ary tree:

We should return its level order traversal:

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

Note:

The depth of the tree is at most 1000.
The total number of nodes is at most 5000.

Solution1: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<vector<int>> levelOrder(Node* root) {

vector<vector<int>> ans;

preorder(root, 0, ans);

return ans;

}

private:

void preorder(Node* root, int d, vector<vector<int>>& ans) {

if (root == nullptr) return;

while (ans.size() <= d) ans.push_back({});

ans[d].push_back(root->val);

for (auto child : root->children)

preorder(child, d + 1, ans);

}

};

Solution2: Iterative

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<vector<int>> levelOrder(Node* root) {

if (!root) return {};

vector<vector<int>> ans;

queue<Node*> q;

q.push(root);

int depth = 0;

while (!q.empty()) {

int size = q.size();

ans.push_back({});

while (size--) {

Node* n = q.front(); q.pop();

ans[depth].push_back(n->val);

for (auto child : n->children)

q.push(child);

}

++depth;

}

return ans;

}

};

花花酱 LeetCode 559. Maximum Depth of N-ary Tree

By zxi on July 14, 2018

Problem

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example, given a 3-ary tree:

We should return its max depth, which is 3.

Note:

The depth of the tree is at most 1000.
The total number of nodes is at most 5000.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 40 ms

class Solution {

public:

int maxDepth(Node* root) {

if (root == nullptr) return 0;

int depth = 0;

for (auto child : root->children)

depth = max(depth, maxDepth(child));

return depth + 1;

}

};

Problem

Given an n-ary tree, return the postorder traversal of its nodes’ values.

For example, given a 3-ary tree:

Return its postorder traversal as: [5,6,3,2,4,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1: Recursive

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<int> postorder(Node* root) {

vector<int> ans;

postorder(root, ans);

return ans;

}

private:

void postorder(Node* root, vector<int>& ans) {

if (!root) return;

for (auto child : root->children)

postorder(child, ans);

ans.push_back(root->val);

}

};

Solution 2: Iterative

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<int> postorder(Node* root) {

if (!root) return {};

vector<int> ans;

stack<Node*> s;

s.push(root);

while (!s.empty()) {

const Node* node = s.top(); s.pop();

ans.push_back(node->val);

for (auto child : node->children)

s.push(child);

}

reverse(begin(ans), end(ans));

return ans;

}

};

Problem

Given an n-ary tree, return the preorder traversal of its nodes’ values.

For example, given a 3-ary tree:

Return its preorder traversal as: [1,3,5,6,2,4].

Note: Recursive solution is trivial, could you do it iteratively?

Solution1: Recursive

// Author: Huahua

// Running time: 48 ms

class Solution {

public:

vector<int> preorder(Node* root) {

vector<int> ans;

preorder(root, ans);

return ans;

}

private:

void preorder(Node* root, vector<int>& ans) {

if (!root) return;

ans.push_back(root->val);

for (const auto& child : root->children)

preorder(child, ans);

}

};

Solution2: Iterative

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

vector<int> preorder(Node* root) {

if (!root) return {};

vector<int> ans;

stack<Node*> s;

s.push(root);

while (!s.empty()) {

const Node* node = s.top(); s.pop();

ans.push_back(node->val);

for (auto it = node->children.rbegin(); it != node->children.rend(); ++it)

s.push(*it);

}

return ans;

}

};

Posts published in “Tree”

花花酱 LeetCode 501. Find Mode in Binary Search Tree

Problem

Solution1: Recursion w/ extra space

Solution2: Recursion w/o extra space

花花酱 LeetCode 429. N-ary Tree Level Order Traversal

Problem

Solution1: Recursion

Solution2: Iterative

花花酱 LeetCode 559. Maximum Depth of N-ary Tree

Problem

Solution: Recursion

Related Problems

花花酱 LeetCode 590. N-ary Tree Postorder Traversal

Problem

Solution 1: Recursive

C++

Solution 2: Iterative

C++

Related Problems

花花酱 LeetCode 589. N-ary Tree Preorder Traversal

Problem

Solution1: Recursive

Solution2: Iterative

Related Problems