题目
题目来源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); } }
题解
前序遍历
144. 二叉树的前序遍历
思路：使用栈来进行前序遍历，每次出栈一个元素的操作都是一致的：先读取出栈的元素值，紧接着出栈节点的右节点先入栈，左节点后入栈。
ps：入栈的节点不为null，先入右节点，后入左节点好处就是每次出栈得到的必是左节点的元素！ public List<Integer> preorderTraversal(TreeNode root) { Deque<TreeNode> stack = new LinkedList<>(); List<Integer> nums = new ArrayList<>(); if(root != null){ stack.push(root);//先将头节点入栈 } while(!stack.isEmpty()){ TreeNode node = stack.pop(); //从栈中读取节点的值(此时就会先读取到左节点的值，之后则是右节点的值) nums.add(node.val); //首先将节点的右节点入栈 if(node.right != null){ stack.push(node.right); } //接着将节点的左节点入栈 if(node.left != null){ stack.push(node.left); } } return nums; }
中序遍历
94. 二叉树的中序遍历
思路：同样是用栈+指针的形式，指针用来寻路，栈中存储的都是待取值的一个个节点。若是当前节点为null，说明已经某个节点的左节点已经走完，走完的相同操作都是出栈一个元素，取到值之后开始继续对右节点进行探索。
//栈中存储的是多个待取值的节点 public List<Integer> inorderTraversal(TreeNode root) { Deque<TreeNode> stack = new LinkedList<>(); List<Integer> nums = new ArrayList<>(); TreeNode cur = root; while(cur != null || !stack.isEmpty()){ //若是节点不为空，则直接入栈 if(cur != null){ stack.push(cur); cur = cur.left;//继续对节点的左节点遍历 }else{ //若是节点为空，表名左节点已经探索结束 //从栈中取出一个元素 cur = stack.pop(); nums.add(cur.val);//存储值 cur = cur.right;//开始对右节点进行相同操作 } } return nums; }
后序遍历
145. 二叉树的后序遍历
思路：与前序遍历方式相同，前序遍历是先出栈取值，接着入栈右节点、左节点；这里的话先取值，接着入栈左节点、右节点，最终将取到的值进行反转。(前序遍历方式：左-右-中，这里取值刚好反过来中-右-左，最终反转即可)
//后序遍历取法 左-右-中 入栈顺序：中-右-左 ，与前序迭代遍历很相似，出栈元素取值。最终我们反转一下取到的值就是后序遍历取值 public List<Integer> postorderTraversal(TreeNode root) { Deque<TreeNode> stack = new LinkedList<>(); List<Integer> nums = new ArrayList<>(); if(root != null){ stack.push(root); } while(!stack.isEmpty()){ TreeNode node = stack.pop(); nums.add(node.val); if(node.left != null){ stack.push(node.left); } if(node.right != null){ stack.push(node.right); } } Collections.reverse(nums); return nums; }
