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 a back-order traversal of the 590.n fork tree in LeetCode. The difficulty is simple.

Tag: “Recursive”, “iterative”, “non-recursive”, “DFS”, “BFS”

Given rootrootroot, the root node of an NNN fork tree, return a back-order 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:,6,3,2,4,1 [5]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: ,6,14,11,7,3,12,8,4,13,9,10,5,1 [2]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> postorder(Node root) {
        dfs(root);
        return ans;
    }
    void dfs(Node root) {
        if (root == null) return;
        for(Node node : root.children) dfs(node); ans.add(root.val); }}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

non-recursive

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

In the process of iteration, record the binary group (CNT = number of traversed child nodes of the current node, node = current node), remove the top element of the stack each time, if the current node has traversed all the child nodes (the number of traversed child nodes is CNT = number of child nodes CNT = number of child nodes CNT = number of child nodes), The value of the current node is added to the answer.

(CNT +1,node)(CNT +1,node)(CNT +1,node) Add the next child node (0, Node.children [CNT])(0, Node.children [CNT])(0, Node.children [CNT]) for the first time.

Code:

class Solution {
    public List<Integer> postorder(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 cnt = (Integer)poll[0]; Node t = (Node)poll[1];
            if (t == null) continue;
            if (cnt == t.children.size()) ans.add(t.val);
            if (cnt < t.children.size()) {
                d.addLast(new Object[]{cnt + 1, t});
                d.addLast(new Object[]{0, t.children.get(cnt)}); }}returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

General “non-recursion”

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> postorder(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) {
                d.addLast(new Object[]{1, t});
                int n = t.children.size();
                for (int i = n - 1; i >= 0; i--) d.addLast(new Object[]{0, t.children.get(i)});
            } else if (loc == 1) { ans.add(t.val); }}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.590 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions 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.