非递归遍历树

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.LinkedList;

public class MainTra {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str = sc.nextLine();
    int[] arr = Arrays.stream(str.split(" ")).mapToInt(Integer::valueOf).toArray();

    Solution so = new Solution();
    TreeNode root = so.creatTree(arr,0);
    ArrayList<Integer> res = so.postTraver(root);
    for(int i=0;i<res.size();i++) {
      System.out.print(res.get(i)+" ");
    }
    System.out.println(System.lineSeparator());
  }
}
/****
 *  思想：构建树的时候，加入isVisit属性，全部默认为false；
 *  先添加root节点进栈；
 *  执行while循环：（1）弹出栈顶节点node；（2）如果visit==true;则添加进入结果，回到while循环；
 *  否则，增加入栈，遵循返过来的顺序和判空，当前节点的visit赋予true。
 */
class Solution {
  // 先序遍历
  public ArrayList<Integer> preTraver(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<>();
    LinkedList<TreeNode> stack = new LinkedList<>();
    stack.add(root);
    while(stack.size()>0) {
      TreeNode node = stack.pollLast();
      if(node.isVisit) {
        res.add(node.val);
      }else { //=============================preTraver（模板，唯一差别部分）======
        // 先序遍历（根左右）进栈：右左根的非空元素依次进去
        if(node.right!=null) {
          stack.add(node.right);
        }
        if(node.left!=null) {
          stack.add(node.left);
        }
        node.isVisit = true;
        stack.add(node);
      }//==========================================================================
    }
    return res;
  }
  // 中序遍历
  public ArrayList<Integer> inTraver(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<>();
    LinkedList<TreeNode> stack = new LinkedList<>();
    stack.add(root);
    while(stack.size()>0) {
      TreeNode node = stack.pollLast();
      if(node.isVisit) {
        res.add(node.val);
      }else {
        // 中序遍历（左根右）进栈：右根左的非空元素依次进去
        if(node.right!=null) {
          stack.add(node.right);
        }
        node.isVisit = true;
        stack.add(node);
        if(node.left!=null) {
          stack.add(node.left);
        }
      }
    }
    return res;
  }
  // 后序遍历
  public ArrayList<Integer> postTraver(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<>();
    LinkedList<TreeNode> stack = new LinkedList<>();
    stack.add(root);
    while(stack.size()>0) {
      TreeNode node = stack.pollLast();
      if(node.isVisit) {
        res.add(node.val);
      }else {
        // 后序遍历（左右根）进栈：根右左的非空元素依次进去
        node.isVisit = true;
        stack.add(node);
        if(node.right!=null) {
          stack.add(node.right);
        }
        if(node.left!=null) {
          stack.add(node.left);
        }
      }
    }
    return res;
  }
  // 构建树
  public TreeNode creatTree(int[] arr,int i) {
    if(i>=arr.length) {
      return null;
    }
    TreeNode root = new TreeNode(arr[i]);
    root.left = creatTree(arr,2*i+1);
    root.right = creatTree(arr,2*i+2);
    return root;
  }

}

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  boolean isVisit;

  public TreeNode(int val) {
    this.val = val;
  }
}