/* 前序递归遍历1. 如果二叉树为null，则直接返回2. 如果二叉树不为null，先访问根节点再访问左子树，最后访问右子树*/public static void preorderTraversalRec(TreeNode root){ if(root == null){ return ; } System.out.print(root.val + " "); preorderTraversalRec(root.left); preorderTraversalRec(root.right);}/*前序迭代遍历用一个辅助stack，总是把右孩子放进栈。*/public static void preorderTraversal(TreeNode root){ if(root == null) return null; Stack stack = new Stack (); stack.push(root); while(!stack.isEmpty()){ TreeNode cur= stack.pop(); System.out.print(cur.val + " "); //关键点：先压入右孩子，再压入左孩子，这样在出栈的时会先打印左孩子，再打印右孩子。 if(cur.right != null){ stack.push(cur.right); } if(cur.left != null){ stack.push(cur.left); } } }/*中序递归遍历1。如果二叉树为null，则直接返回2. 如果二叉树不为null，则先访问左子树，再访问根节点，最后访问右子树。*/public static void inorderTravelsalRec(TreeNode root){ if(root == null){ return ; } inorderTravelsalRec(root.left); System.out.print(root.val + " "); inorderTravelsalRec(root.right);}/*中序迭代遍历用栈先把根节点的所有左孩子都添加到栈内，然后输出栈顶元素，再处理栈顶元素的右子树*/publiv static void inorderTravelsal(TreeNode root){ if(root == null){ return ; } stack stack = new Stack (); TreeNode cur = root; while(true){ while(cur != null){ //先添加所有的左孩子到栈内 stack.push(cur); cur = cur.left; } if(stack.isEmpty()){ break; } //因为此时已经没有左孩子，所以输出栈顶元素 cur = stack.pop(); System.out.print(cur.val + " "); cur = cur.right; }}/*后序递归遍历1.如果二叉树为null，则直接返回；2.如果二叉树不为null，先访问左子树，再访问右子树，最后访问根节点*/public static void postorderTravelsalRec(TreeNode root){ if(root == null){ return ; } postorderTravelsalRec(root.left); postorderTravelsalRec(root.right); System.out.print(root.val + " ");}/*后序迭代遍历*/public static void postorderTravelRec(TreeNode root){ if(root == null){ return ; } Stack s = new Stack ();//第一个stack用于添加node和他的左右孩子 Stack output = new Stack ();//第二个stack用于翻转第一个stack输出 s.push(root); while(!s.isEmpty()){ TreeNode cur = s.pop(); output.push(cur); //把栈顶元素添加到第二个stack if(cur.left != null){ s.push(cur.left); } if(cur.right != null){ s.push(cur.right); } while(!output.isEmpty()){//遍历输出第二个stack，即为后序遍历 System.out.print(output.pop().val + " "); } } }