Posts tagged as “postorder”

花花酱 LeetCode 1519. Number of Nodes in the Sub-Tree With the Same Label

By zxi on July 18, 2020

Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [a_i, b_i], which means there is an edge between nodes a_i and b_i in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the i^th node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.

Example 3:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]

Example 4:

1 2	<strong>Input:</strong> n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa" <strong>Output:</strong> [1,2,1,1,2,1]

Example 5:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
Output: [6,5,4,1,3,2,1]

Constraints:

1 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
labels.length == n
labels is consisting of only of lower-case English letters.

Solution: Post order traversal + hashtable

For each label, record the count. When visiting a node, we first record the current count of its label as before, and traverse its children, when done, increment the current count, ans[i] = current – before.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> countSubTrees(int n, vector<vector<int>>& edges,

string_view labels) {

vector<vector<int>> g(n);

for (const auto& e : edges) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

vector<int> seen(n);

vector<int> count(26);

vector<int> ans(n);

function<void(int)> postOrder = [&](int i) {

if (seen[i]++) return;

int before = count[labels[i] - 'a'];

for (int j : g[i]) postOrder(j);

ans[i] = ++count[labels[i] - 'a'] - before;

};

postOrder(0);

return ans;

}

};

Java

// Author: Huahua

class Solution {

private List<List<Integer>> g;

private String labels;

private int[] ans;

private int[] seen;

private int[] count;

public int[] countSubTrees(int n, int[][] edges, String labels) {

this.g = new ArrayList<List<Integer>>(n);

this.labels = labels;

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

this.g.add(new ArrayList<Integer>());

for (int[] e : edges) {

this.g.get(e[0]).add(e[1]);

this.g.get(e[1]).add(e[0]);

}

this.ans = new int[n];

this.seen = new int[n];

this.count = new int[26];

this.postOrder(0);

return ans;

}

private void postOrder(int i) {

if (this.seen[i]++ > 0) return;

int before = this.count[this.labels.charAt(i) - 'a'];

for (int j : this.g.get(i)) this.postOrder(j);

this.ans[i] = ++this.count[this.labels.charAt(i) - 'a'] - before;

}

Python3

# Author: Huahua

class Solution:

def countSubTrees(self, n: int, edges: List[List[int]],

labels: str) -> List[int]:

g = [[] for _ in range(n)]

for u, v in edges:

g[u].append(v)

g[v].append(u)

seen = [False] * n

count = [0] * 26

ans = [0] * n

def postOrder(i):

if seen[i]: return

seen[i] = True

before = count[ord(labels[i]) - ord('a')]

for j in g[i]: postOrder(j)

count[ord(labels[i]) - ord('a')] += 1

ans[i] = count[ord(labels[i]) - ord('a')] - before

postOrder(0)

return ans

花花酱 LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal

By zxi on August 23, 2018

Problem

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note:

1 <= pre.length == post.length <= 30
pre[] and post[] are both permutations of 1, 2, ..., pre.length.
It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

Solution: Recursion

pre = [(root) (left-child) (right-child)]

post = [(left-child) (right-child) (root)]

We need to recursively find the first node in pre.left-child from post.left-child

e.g.

pre = [(1), (2,4,5), (3,6,7)]

post = [(4,5,2), (6,7,3), (1)]

First element of left-child is 2 and the length of it is 3.

root = new TreeNode(1)
root.left = build((2,4,5), (4,5,2))
root.right = build((3,6,7), (6,7,3))

Time complexity: O(n^2)

Space complexity: O(n)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {

return constructFromPrePost(cbegin(pre), cend(pre), cbegin(post), cend(post));

}

private:

typedef vector<int>::const_iterator VIT;

TreeNode* constructFromPrePost(VIT pre_l, VIT pre_r, VIT post_l, VIT post_r) {

if (pre_l == pre_r) return nullptr;

TreeNode* root = new TreeNode(*pre_l);

++pre_l;

--post_r;

if (pre_l == pre_r) return root;

VIT post_m = next(find(post_l, post_r, *pre_l));

VIT pre_m = pre_l + (post_m - post_l);

root->left = constructFromPrePost(pre_l, pre_m, post_l, post_m);

root->right = constructFromPrePost(pre_m, pre_r, post_m, post_r);

return root;

}

};

Time complexity: O(n^2)

Space complexity: O(n)

"""

Author: Huahua

Running time: 60 ms

"""

class Solution:

def constructFromPrePost(self, pre, post):

def build(i, j, n):

if n <= 0: return None

root = TreeNode(pre[i])

if n == 1: return root

k = j

while post[k] != pre[i + 1]: k += 1

l = k - j + 1

root.left = build(i + 1, j, l)

root.right = build(i + l + 1, k + 1, n - l - 1)

return root

return build(0, 0, len(pre))

Time complexity: O(n)

"""

Author: Huahua

Running time: 52 ms (beats 100%)

"""

class Solution:

def constructFromPrePost(self, pre, post):

def build(i, j, n):

if n <= 0: return None

root = TreeNode(pre[i])

if n == 1: return root

k = index[pre[i + 1]]

l = k - j + 1

root.left = build(i + 1, j, l)

root.right = build(i + l + 1, k + 1, n - l - 1)

return root

index = {}

for i in range(len(pre)):

index[post[i]] = i

return build(0, 0, len(pre))

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

By zxi on July 12, 2018

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 a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

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

Solution 1:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

vector<int> ans;

postorderTraversal(root, ans);

return ans;

}

void postorderTraversal(TreeNode* root, vector<int>& ans) {

if (!root) return;

postorderTraversal(root->left, ans);

postorderTraversal(root->right, ans);

ans.push_back(root->val);

}

};

Solution 2:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

if (!root) return {};

vector<int> ans;

const vector<int> l = postorderTraversal(root->left);

const vector<int> r = postorderTraversal(root->right);

ans.insert(ans.end(), l.begin(), l.end());

ans.insert(ans.end(), r.begin(), r.end());

ans.push_back(root->val);

return ans;

}

};

Solution 3:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

if (!root) return {};

deque<int> ans;

stack<TreeNode*> s;

s.push(root);

while (!s.empty()) {

TreeNode* n = s.top();

s.pop();

ans.push_front(n->val); // O(1)

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

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

}

return vector<int>(ans.begin(), ans.end());

}

};

Posts tagged as “postorder”

花花酱 LeetCode 1519. Number of Nodes in the Sub-Tree With the Same Label

Solution: Post order traversal + hashtable

C++

Java

Python3

花花酱 LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal

Problem

Solution: Recursion

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

Problem

Solution 1: Recursive

C++

Solution 2: Iterative

C++

Related Problems

花花酱 LeetCode 332. Reconstruct Itinerary

花花酱 LeetCode 145. Binary Tree Postorder Traversal

Problem:

Solution 1:

Solution 2:

Solution 3: