Subject to understand

Given a binary tree, return its backward traversal.

A post-order traversal of a binary tree is an output of nodes left > right > root.

Thought analysis

Before we carried out recursive form of the problem solving process, the direction is as follows [Luffy] Leetcode – recursive call to solve the binary tree traversal

The following train of thought analysis:

We need to define three variables: ANS: the final return result, S1: the value of the temporary variable in the recursion, s2: the state of the program & the position of the program to which the recursion occurred,

In the while loop, when S1 is not empty, the program states are divided into 0, 1, and 2. 0 is the left subtree, 1 is the right subtree, and 2 is the root node.

Each time we go to the left subtree, the program state is ultimately determined based on whether there are any left subtrees left, and whether we append values to S1

Each time we go to the right subtree, we also determine the final state of the program based on whether there is a right subtree and whether we append the value to S1

Each time the root node is visited, the topmost element is removed from the top of the S1 stack and placed in the final return result.

Proceed in turn until the program is complete.

Diagram analysis

Code implementation


var postorderTraversal = function (root) {
    if(! root)return [];
    const ans = [];
    const s1 = []; // The recursive value
    const s2 = []; // Program status

    s1.push(root);
    s2.push(0);

    while(! (s1.length ===0)) {
        const status = s2.pop();
        const len = s1.length;
        switch (status) {
            case 0:
                s2.push(1);
                const left = s1[len - 1].left;
                if (left) {
                    s1.push(left);
                    s2.push(0);
                }
                break;
            case 1:
                s2.push(2);
                const right = s1[len - 1].right;
                if (right) {
                    s1.push(right);
                    s2.push(0);
                }
                break;
            case 2:
                ans.push(s1.pop().val);
                break; }}return ans;
};
Copy the code

Other Relevant instructions

Recursive method and iterative method actually run meaning is almost the same but the form of expression is not quite the same, theoretically speaking, all of our recursive method to achieve, can use iterative method to write different forms of code, if you want to improve their code level, this kind of exercise is indispensable oh ~ ~ ~