题目
题目来源leetcode
144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
本地调试代码：
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() { } TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } class Solution { public static void main(String[] args) { TreeNode node5 = new TreeNode(5, null, null); TreeNode node4 = new TreeNode(4, null, node5); TreeNode node2 = new TreeNode(2, node4, null); TreeNode node3 = new TreeNode(3, null, null); TreeNode node1 = new TreeNode(1, node2, node3); morrisPre(node1); } }
题解
思路：同样使用栈，按照对应的遍历方式来将所有的节点存储，接着来进行依次出栈取值，这里比较细节的一点就是要出栈取值的节点后会跟随这一个null值用于进行标识。
前序遍历
//统一迭代：前序遍历 public List<Integer> preorderTraversal(TreeNode root) { Deque<TreeNode> stack = new LinkedList<>();//根据指定的遍历顺序来进行存放 List<Integer> result = new ArrayList<>(); if(root != null){ stack.push(root); } while(!stack.isEmpty()){ TreeNode node = stack.peek(); if(node != null){ stack.pop(); //前序遍历：在栈中存储方式为右-左-中 if(node.right != null){ stack.push(node.right); } if(node.left != null){ stack.push(node.left); } //null则为之后记录遍历值时的标识 stack.push(node); stack.push(null); }else{ stack.pop();//先将null标识弹出，之后直接来统计拿到值 TreeNode valNode = stack.pop(); result.add(valNode.val); } } return result; }
中序遍历
//统一迭代：中序遍历 public List<Integer> postorderTraversal(TreeNode root) { Deque<TreeNode> stack = new LinkedList<>();//根据指定的遍历顺序来进行存放 List<Integer> result = new ArrayList<>(); if(root != null){ stack.push(root); } while(!stack.isEmpty()){ TreeNode node = stack.peek(); if(node != null){ stack.pop(); //中序遍历：在栈中存储方式为右-中-左 if(node.right != null){ stack.push(node.right); } stack.push(node); stack.push(null); if(node.left != null){ stack.push(node.left); } }else{ stack.pop();//先将null标识弹出，之后直接来统计拿到值 TreeNode valNode = stack.pop(); result.add(valNode.val); } } return result; }
后序遍历
//统一迭代：后序遍历 public List<Integer> postorderTraversal(TreeNode root) { Deque<TreeNode> stack = new LinkedList<>();//根据指定的遍历顺序来进行存放 List<Integer> result = new ArrayList<>(); if(root != null){ stack.push(root); } while(!stack.isEmpty()){ TreeNode node = stack.peek(); if(node != null){ stack.pop(); stack.push(node); stack.push(null); //中序遍历：在栈中存储方式为右-中-左 if(node.right != null){ stack.push(node.right); } if(node.left != null){ stack.push(node.left); } }else{ stack.pop();//先将null标识弹出，之后直接来统计拿到值 TreeNode valNode = stack.pop(); result.add(valNode.val); } } return result; }
