花花酱 LeetCode 199. Binary Tree Right Side View

By zxi on November 28, 2021

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

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

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Solution: Pre-order traversal

By using pre-order traversal, the right most node will be the last one to visit in each level.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> rightSideView(TreeNode* root) {

vector<int> ans;

function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int d) {

if (!root) return;

if (ans.size() < d + 1) ans.push_back(0);

ans[d] = root->val;

dfs(root->left, d + 1);

dfs(root->right, d + 1);

};

dfs(root, 0);

return ans;

}

};

花花酱 LeetCode 103. Binary Tree Zigzag Level Order Traversal

By zxi on August 20, 2019

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Solution 1: DFS

in order traversal using DFS and reverse the result of even levels.

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

C++

// Author: Huahua, 0ms, 15.1 MB

class Solution {

public:

vector<vector<int> > zigzagLevelOrder(TreeNode *root) {

vector<vector<int>> ans;

function<void(TreeNode*, int)> dfs = [&](TreeNode* r, int d) {

if (!r) return;

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

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

dfs(r->right, d + 1);

dfs(r->left, d + 1);

};

dfs(root, 0);

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

reverse(begin(ans[i]), end(ans[i]));

return ans;

}

};

Solution 2: BFS

Expend/append in order for even levels and doing that in reverse order for odd levels.

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> zigzagLevelOrder(TreeNode *root) {

if (!root) return {};

vector<vector<int>> ans;

deque<TreeNode*> q;

q.push_back(root);

int d = 0;

while (q.size()) {

ans.push_back({});

auto cur = &ans.back();

deque<TreeNode*> next;

while (q.size()) {

if (d % 2) {

TreeNode* node = q.back();

q.pop_back();

cur->push_back(node->val);

if (node->right) next.push_front(node->right);

if (node->left) next.push_front(node->left);

} else {

TreeNode* node = q.front();

q.pop_front();

cur->push_back(node->val);

if (node->left) next.push_back(node->left);

if (node->right) next.push_back(node->right);

}

++d;

q.swap(next);

}

return ans;

}

};

花花酱 LeetCode 1161. Maximum Level Sum of a Binary Tree

By zxi on August 17, 2019

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level X such that the sum of all the values of nodes at level X is maximal.

Example 1:

Input: [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

Note:

The number of nodes in the given tree is between 1 and 10^4.
-10^5 <= node.val <= 10^5

Solution: HashTable

Use a hash table / array to store the level sum.

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

C++

// Author: Huahua, 232 ms, 70.2 ms

class Solution {

public:

int maxLevelSum(TreeNode* root) {

vector<int> sums;

function<void(TreeNode*, int)> preorder = [&](TreeNode* n, int d) {

if (!n) return;

while (sums.size() <= d) sums.push_back(0);

sums[d] += n->val;

preorder(n->left, d + 1);

preorder(n->right, d + 1);

};

preorder(root, 1);

int max_sum = sums[1];

int ans = 1;

for (int i = 2; i < sums.size(); ++i)

if (sums[i] > max_sum) {

max_sum = sums[i];

ans = i;

}

return ans;

}

};

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

}

};

Posts tagged as “level”

花花酱 LeetCode 199. Binary Tree Right Side View

Solution: Pre-order traversal

C++

花花酱 LeetCode 103. Binary Tree Zigzag Level Order Traversal

Solution 1: DFS

C++

Solution 2: BFS

C++

Related Problems

花花酱 LeetCode 1161. Maximum Level Sum of a Binary Tree

Solution: HashTable

C++

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

Problem

Solution1: Recursion

Solution2: Iterative