二叉树遍历是比较基础的常规操作,没什么难度。主要有三种遍历方式
- 前序遍历:(根、左、右)
- 中序遍历:(左、根、右)
- 后续遍历:(左、右、根)
递归的方式很简单、这里不多说明。主要说明一下利用栈先进后出的特性非递归方式遍历
前序遍历:
1.对于任意节点current,若该节点不为空则访问该节点后再将节点压栈,并将左子树节点置为current,重复此操作,直到current为空。
2.若左子树为空,栈顶节点出栈,将该节点的右子树置为current
3.重复1、2步操作,直到current为空且栈内节点为空。
中序遍历:
1.对于任意节点current,若该节点不为空则将该节点压栈,并将左子树节点置为current,重复此操作,直到current为空。
2.若左子树为空,栈顶节点出栈,访问节点后将该节点的右子树置为current
3.重复1、2步操作,直到current为空且栈内节点为空。
后序遍历:
利用栈迭代后再反转,后序遍历的顺序为左、右、根, 其逆序为根、右、左。利用栈可以很简单的先对二叉树按照其逆序的方式正常进行遍历后、再将遍历的顺序反转就得到其后序遍历序列
//整体代码如下 public class Solution { /** * * @param root TreeNode类 the root of binary tree * @return int整型二维数组 */ public int[][] threeOrders (TreeNode root) { int size = getSize(root); if(size == 0) return new int[0][0]; int[][] result = new int[3][size]; //先序遍历 result[0] = preOrderByStack(root, size); //中序遍历 result[1] = inOrderByStack(root, size); //后续遍历二叉树 result[2] = postOrderByStack(root, size); return result; } //利用栈先序遍历二叉树 private int[] preOrderByStack(TreeNode root, int size){ int[] arr = new int[size]; int idx = 0; //初始化栈 Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while(!stack.isEmpty() || cur != null){ if(cur != null){ //遍历当前节点后、压栈 arr[idx++] = cur.val; stack.push(cur); cur = cur.left; } if(cur == null){ //栈顶节点出栈、当前节点置为右子树 TreeNode temp = stack.pop(); cur = temp.right; } } return arr; } //利用栈中序遍历二叉树 private int[] inOrderByStack(TreeNode root, int size){ int[] arr = new int[size]; int idx = 0; //初始化栈 Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while(!stack.isEmpty() || cur != null){ if(cur != null){ //节点压栈 stack.push(cur); cur = cur.left; } if(cur == null){ //栈顶节点出栈 TreeNode temp = stack.pop(); //访问当前节点后、将cur置为右子树 arr[idx++] = temp.val; cur = temp.right; } } return arr; } //利用栈后续遍历二叉树(利用栈迭代反转) public int[] postOrderByStack(TreeNode root, int size){ int[] arr = new int[size]; int idx = size - 1; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()){ TreeNode temp = stack.pop(); arr[idx--] = temp.val; if(temp.left != null) stack.push(temp.left); if(temp.right != null) stack.push(temp.right); } return arr; } private int getSize(TreeNode root){ if(root == null) return 0; int sizeL = getSize(root.left); int sizeR = getSize(root.right); return sizeL + sizeR + 1; } }