PostOrder Traversal с использованием одного стека

При предварительном обходе код

• отображает данные для текущего узла
• обходит левое поддерево
• пересекает правое поддерево

При обратном обходе код

• обходит левое поддерево
• пересекает правое поддерево
• отображает данные для текущего узла

Таким образом, разница в том, что данные должны храниться в стеке при выполнении обхода в обратном порядке, чтобы их можно было распечатать последними. Есть несколько различных способов сделать это. Один из способов — изменить реализацию стека, чтобы различать дочерние указатели и указатели на данные.

Когда дочерний указатель извлекается, действия

• нажмите текущий узел как указатель данных
• нажмите правый узел как дочерний указатель
• нажмите левый узел как дочерний указатель

Когда указатель данных извлекается, действие

• отображать данные для узла

Затем обход начинается с нажатия корневого узла в качестве дочернего указателя.

Хотя код сложнее, итеративный обратный порядок может быть более интуитивным, чем другие обходы, потому что другие были подвергнуты рефакторингу, а этот не может быть подвергнут аналогичному рефакторингу.

Используйте первое решение здесь: https://articles.leetcode.com/binary-tree-post-order-traversal/

Интуиция такова, что у рекурсивных функций есть информация, которой нет у итерационных методов, в основном о направлении обхода. Когда рекурсивная функция выполняется или откатывается, она знает, откуда она взялась, по какой строке кода она выполняется. IE, если вы печатаете или обрабатываете текущий узел, вы знаете, что уже посетили дочерние элементы, потому что они уже вызывались рекурсивно.

Итеративное решение может отслеживать его с помощью «предыдущего» указателя, поэтому вы видите проверки «если предыдущий не является дочерним элементом текущего узла», то это означает, что вы перемещаетесь вниз, и вам нужно идти влево. Другие возможности заключаются в том, что предыдущее исходило из левого или правого дочернего узла. Как только все случаи будут обработаны, у вас есть решение.

Ниже приведен фрагмент кода PostOrder Traversal с использованием одного стека в java.

public class PostOrderWithoutRecurssion {

    static Stack<Node> stack = new Stack<Node>();

    static class Node{
        int data;
        int status;
        Node left, right;

        Node(int data){
            this.data = data;
            this.status=0;
        }
    }//end class Node

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.left.left.left = new Node(8);
        root.left.left.right = new Node(9);

        postOrderWithoutRecurssion(root);
    }//end main

    public static void postOrderWithoutRecurssion(Node root) {
        Node temp = root;

        while(temp!=null || stack.size()>0) {

            while(temp!=null) {
                temp.status = 1;
                stack.push(temp);
                temp = temp.left;
            }

            temp = stack.pop();

            if(null==temp.left && null == temp.right) {
                temp.status = 2;
                System.out.println(temp.data);
            }else if(null != temp.right) {
                if(temp.left.status==2 && temp.right.status==2) {
                    temp.status = 2;
                    System.out.println(temp.data);
                    temp = null;
                }else {
                    if(temp.status!=1) {
                        temp.status = 1;
                        stack.push(temp);
                    }else {
                        stack.push(temp);
                    }
                }
            }

            if(null!=temp) {
                temp = temp.right;    
            }

        }
    }//end postOrderWithoutRecurssion
}