Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

This is the prior traversal of the 589.n fork tree on LeetCode. The difficulty is simple.

Tag: “Tree search”, “recursion”, “iteration”

Given rootrootroot, the root node of an NNN fork tree, return a sequential traversal of its node values.

The NNN fork tree is serialized in the input as a sequential traversal, with each set of child nodes separated by null values (see example).

Example 1:

Input: root = [1, null, 3 4-trichlorobenzene, null, 5, 6] output:,3,5,6,2,4 [1]Copy the code

Example 2:

Input: root = [1, null, 2, 5-tetrafluorobenzoic, null, null, 6, 7, null, 8, null, 9, 10, null, null, 11, null, 12, null, 13, null, null, 14] output: ,2,3,6,7,11,14,4,8,12,5,9,13,10 [1]Copy the code

Tip:

  • The total number of nodes is in the range [0 104][0, 10^4][0 104]

  • 0 < = N o d e . v a l < = 1 0 4 0 <= Node.val <= 10^4
  • NNN The height of the fork tree is less than or equal to 100010001000

Progression: recursion is easy, can you use iterative method to complete this problem?

recursive

General practice, not to repeat.

Code:

class Solution {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        dfs(root);
        return ans;
    }
    void dfs(Node root) {
        if (root == null) return ;
        ans.add(root.val);
        for(Node node : root.children) dfs(node); }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1), ignoring the extra space overhead caused by recursion

The iteration

In this case, the stack is used to simulate the recursive process.

The binary group (node = current node, CNT = number of child nodes traversed by the current node) is recorded in the iteration process, and the top element of the stack is taken out each time. If the current node is the first queue exit (the number of child nodes traversed is CNT = 0CNt = 0CNt =0), the value of the current node is added to the answer. (node, CNT +1)(node, CNT +1)(node, CNT +1) Children [CNT],0)(Node. Children [CNT],0)(Node. Children [CNT],0)(Node.

Code;

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        Deque<Object[]> d = new ArrayDeque<>();
        d.addLast(new Object[]{root, 0});
        while(! d.isEmpty()) { Object[] poll = d.pollLast(); Node t = (Node)poll[0]; Integer cnt = (Integer)poll[1];
            if (t == null) continue;
            if (cnt == 0) ans.add(t.val);
            if (cnt < t.children.size()) {
                d.addLast(new Object[]{t, cnt + 1});
                d.addLast(new Object[]{t.children.get(cnt), 0}); }}returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

General “recursive” to “iterative”

A more general alternative to recursion-to-iteration is to directly simulate the system performing recursion.

Because modern compilers have done so much to optimize recursion, this technique is no longer necessary.

The loC of current stack frame position is recorded in the iteration process, and corresponding operations are performed at each state flow node.

Code:

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        Deque<Object[]> d = new ArrayDeque<>();
        d.addLast(new Object[]{0, root});
        while(! d.isEmpty()) { Object[] poll = d.pollLast(); Integer loc = (Integer)poll[0]; Node t = (Node)poll[1];
            if (t == null) continue;
            if (loc == 0) {
                ans.add(t.val);
                d.addLast(new Object[]{1, t});
            } else if (loc == 1) {
                int n = t.children.size();
                for (int i = n - 1; i >= 0; i--) {
                    d.addLast(new Object[]{0, t.children.get(i)}); }}}returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

The last

This is the No.589 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.