二叉树的先中后序，非递归实现

先序遍历非递归实现

//先将树的右节点加入，再将树的左节点加入即可，因为出栈顺序是相反的 List<Integer> list = new ArrayList<>(); Stack<TreeNode> s = new Stack<TreeNode>(); public List<Integer> preorderTraversal(TreeNode root) { if (root == null) { return list; } s.add(root); while (!s.isEmpty()) { TreeNode top = s.pop(); list.add(top.val); if (top.right != null) { s.push(top.right); } if (top.left != null) { s.push(top.left); } } return list; }

中序遍历

//一直遍历左节点到叶子节点，然后一直出栈，遇到有右孩子节点的节点，将它压入栈中，停止出栈，实际上，出栈就已经出了左孩子和根，再加入右孩子节点，把它当成一个树的根节点，继续相同的操作，最后就可以完成中序遍历 List<Integer> list = null; public List<Integer> inorderTraversal(TreeNode root) { list = new ArrayList<Integer>(); Stack<TreeNode> sta = new Stack<TreeNode>(); if (root == null) { return list; } sta.push(root); while (!sta.isEmpty()) { TreeNode top = sta.pop(); sta.push(top); TreeNode left = top.left; while (left != null) {//一直遍历左孩子，压入栈中 sta.push(left); left = left.left; } while (!sta.empty()) {//循环出栈 top = sta.pop(); list.add(top.val); if (top.right != null) {//如果栈顶的节点右孩子不为空，直接压入栈中，停止出栈 sta.push(top.right); break; } } } return list; }

后序遍历

//使用一个栈保存结果就好 public List<Integer> postorderTraversal(TreeNode root) { list = new ArrayList<Integer>(); Stack<TreeNode> sta = new Stack<TreeNode>(); Stack<TreeNode> res = new Stack<>(); if (root == null) { return list; } sta.push(root); while (!sta.isEmpty()) { TreeNode top = sta.pop(); res.push(top); if (top.left != null) { sta.push(top.left); } if (top.right != null) { sta.push(top.right); } } while (!res.isEmpty()) { list.add(res.pop().val); } return list; }