LeetCode 589 - N-ary Tree Preorder Traversal


https://leetcode.com/problems/n-ary-tree-preorder-traversal/
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?
https://leetcode.com/problems/n-ary-tree-preorder-traversal/discuss/147955/Java-Iterative-and-Recursive-Solutions
    public List<Integer> preorder(Node root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        
        Stack<Node> stack = new Stack<>();
        stack.add(root);
        
        while (!stack.empty()) {
            root = stack.pop();
            list.add(root.val);
            for (int i = root.children.size() - 1; i >= 0; i--)
                stack.add(root.children.get(i));
        }
        
        return list;
    }
}
Recursive Solution
class Solution {
    public List<Integer> list = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        if (root == null)
            return list;
        
        list.add(root.val);
        for(Node node: root.children)
            preorder(node);
                
        return list;
    }
https://leetcode.com/problems/n-ary-tree-preorder-traversal/discuss/277302/Java-iterative-and-recursive
List<Integer> res = new ArrayList<>();

public List<Integer> preorder(Node root) {
  preorderHelper(root);
  return res;
}

public void preorderHelper(Node root) {
  if (root == null) {
    return;
  }
  int val = root.val;
  res.add(val);
  List<Node> childs = root.children;
  for (int i = 0; i < childs.size(); i++) {
    preorderHelper(childs.get(i));
  }
}


public List<Integer> preorder(Node root) {
  Stack<Node> stack = new Stack<>();
  stack.push(root);
  List<Integer> res = new ArrayList<>();
  if (root == null) {
    return res;
  }
  while (!stack.isEmpty()) {
    Node curr = stack.pop();
    res.add(curr.val);
    List<Node> childs = curr.children;
    int size = childs.size() - 1;
    while (!childs.isEmpty()) {
      stack.add(childs.remove(size));
      size--;
    }
  }
  return res;
}
https://leetcode.com/problems/n-ary-tree-preorder-traversal/discuss/169079/Java-Time-O(N)-and-space-O(N)-recursive-iterative-solution-using-helper-method
  1. iterative solution idea is same as Binary tree.
  2. as it is satck, we need push element in stack from last to 0 index. like in binary tree righ then left.
  3. for more details - https://leetcode.com/problems/binary-tree-preorder-traversal/discuss/168807/Java-O(N)-solution-recursion-and-using-loop-with-explanation
    public List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<>();
  return helper(root, result);
        
    }
    private static List<Integer> helper(Node root, List<Integer> result) {
  if(root != null){
   result.add(root.val);
   for(Node child : root.children){
    helper(child, result);
   }
  }
  return result;
 }
    public List<Integer> preorder(Node root) {
       List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
  Stack<Node> stack = new Stack<>();
  stack.push(root);
  while(! stack.isEmpty()){
   Node current = stack.pop();
   result.add(current.val);
   for(int i = current.children.size() -1 ; i >=0 ; i--){
    stack.push(current.children.get(i));
   }
  }
  return result;
        
    }

LeetCode 590 - N-ary Tree Postorder Traversal


https://leetcode.com/problems/n-ary-tree-postorder-traversal/
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?
https://leetcode.com/problems/n-ary-tree-postorder-traversal/discuss/174665/Java-Iterative-Solution-Using-Two-Stacks.
The iterative solution is similar to the pre-order's, except for when to add the root to the list. The second stack is usd to store the node that pops from the first stack.
    public List<Integer> postorder(Node root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null) return list;
        
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        stack1.add(root);
        
        while(!stack1.empty())
        {
            Node top = stack1.pop();
            stack2.push(top); 
            for(int i = 0; i < top.children.size(); i++)
                stack1.push(top.children.get(i));
        }
        
        while(!stack2.empty())
            list.add(stack2.pop().val);
        
        return list;
    }

https://leetcode.com/problems/n-ary-tree-postorder-traversal/discuss/147959/Java-Iterative-and-Recursive-Solutions
    public List<Integer> postorder(Node root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        
        Stack<Node> stack = new Stack<>();
        stack.add(root);
        
        while(!stack.isEmpty()) {
            root = stack.pop();
            list.add(root.val);
            for(Node node: root.children)
                stack.add(node);
        }
        Collections.reverse(list);
        return list;
    }
}
Recursive
class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> postorder(Node root) {
        if (root == null)
            return list;
        
        for(Node node: root.children)
            postorder(node);
        
        list.add(root.val);
        
        return list;
    }




LeetCode 601 - Human Traffic of Stadium


https://hzhou.me/leetcode/leetcode-human-traffic-of-stadium
X city built a new stadium, each day many people visit it and the stats are saved as these columns: iddatepeople
Please write a query to display the records which have 3 or more consecutive rows and the amount of people more than 100(inclusive).
For example, the table stadium:
1
2
3
4
5
6
7
8
9
10
11
12
+------+------------+-----------+
| id   | date       | people    |
+------+------------+-----------+
| 1    | 2017-01-01 | 10        |
| 2    | 2017-01-02 | 109       |
| 3    | 2017-01-03 | 150       |
| 4    | 2017-01-04 | 99        |
| 5    | 2017-01-05 | 145       |
| 6    | 2017-01-06 | 1455      |
| 7    | 2017-01-07 | 199       |
| 8    | 2017-01-08 | 188       |
+------+------------+-----------+
For the sample data above, the output is:
1
2
3
4
5
6
7
8
+------+------------+-----------+
| id   | date       | people    |
+------+------------+-----------+
| 5    | 2017-01-05 | 145       |
| 6    | 2017-01-06 | 1455      |
| 7    | 2017-01-07 | 199       |
| 8    | 2017-01-08 | 188       |
+------+------------+-----------+
Note:
Each day only have one row record, and the dates are increasing with id increasing.


select distinct s1.*
from stadium s1, stadium s2, stadium s3
where s1.people >= 100 and
s2.people >= 100 and
s3.people >= 100 and
(
    (s1.id + 1 = s2.id and s1.id + 2 = s3.id) or
    (s1.id - 1 = s2.id and s1.id + 1 = s3.id) or
    (s1.id - 2 = s2.id and s1.id - 1 = s3.id)
)
​
order by s1.id asc;
https://knarfeh.com/2014/03/11/leetcode/Database/leetcode-601-Human-Traffic-of-Stadium/
SELECT s1.id as id, s1.date as date, s1.people as people
from stadium as s1, stadium as s2, stadium as s3 WHERE
((s1.id = s2.id-1 AND s2.id = s3.id-1) OR
(s2.id = s1.id-1 AND s1.id = s3.id-1) OR
(s2.id = s3.id-1 AND s3.id = s1.id-1)) AND
s1.people>=100 AND s2.people>=100 AND s3.people>=100
GROUP BY s1.id;
http://www.yuanrengu.com/index.php/201707132.html

https://www.youtube.com/watch?v=Kiz9RPo3Fdc

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts