二叉树前中后序遍历

　　来源：力扣（LeetCode）
　　前序遍历链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
　　中序遍历链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
　　后序遍历链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/ 题目描述
　　二叉树的前序遍历节点访问顺序：根节点、左节点、右节点
　　二叉树的中序遍历节点访问顺序：左节点、根节点、右节点
　　二叉树的后序遍历节点访问顺序：左节点、右节点、根节点题目分析
　　二叉树前中后序遍历主要提供了两种方法： 迭代 递归 前序遍历代码实现public class PreOrder {       public static void main(String[] args) {         PreOrder preOrder = new PreOrder(); //        TreeNode root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));         TreeNode root = null;         preOrder.preorderTraversal(root);         preOrder.preorder2(root);     }       /**      * 迭代算法      *      * @param root      * @return      */     public List preorder2(TreeNode root) {         List list = new ArrayList();          if(root == null){             return list;         }          LinkedList stack = new LinkedList();         stack.add(root);          while (!stack.isEmpty()) {             TreeNode treeNode = stack.getLast();             list.add(treeNode.val);             stack.removeLast();             if (treeNode.right != null) {                 stack.add(treeNode.right);             }             if (treeNode.left != null) {                 stack.add(treeNode.left);             }          }          System.out.println(list);         return list;     }       /**      * 递归      *      * @param root      * @return      */     public List preorderTraversal(TreeNode root) {         List list = new ArrayList();          order(root, list);         System.out.println(list);         return list;     }      private void order(TreeNode root, List list) {         if (root == null) {             return;         }         list.add(root.val);         if (root.left != null) {             order(root.left, list);         }         if (root.right != null) {             order(root.right, list);         }     }   }中序遍历代码实现public class MiddleOrder {       public static void main(String[] args) {         MiddleOrder preOrder = new MiddleOrder();         TreeNode root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null)); //        TreeNode root = null;         preOrder.preorderTraversal(root);         preOrder.preorder2(root);     }       /**      * 迭代算法      *      * @param root      * @return      */     public List preorder2(TreeNode root) {         List list = new ArrayList();          if (root == null) {             return list;         }         LinkedList stack = new LinkedList();          while (root != null || !stack.isEmpty()) {             while (root != null) {                 stack.addLast(root);                 root = root.left;             }             root = stack.removeLast();             list.add(root.val);             root = root.right;         }          System.out.println(list);         return list;     }       /**      * 递归      *      * @param root      * @return      */     public List preorderTraversal(TreeNode root) {         List list = new ArrayList();          order(root, list);         System.out.println(list);         return list;     }      private void order(TreeNode root, List list) {         if (root == null) {             return;         }         if (root.left != null) {             order(root.left, list);         }         list.add(root.val);         if (root.right != null) {             order(root.right, list);         }     }   }后序遍历代码实现public class AfterOrder {       public static void main(String[] args) {         AfterOrder preOrder = new AfterOrder();         TreeNode root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null)); //        TreeNode root = null;         preOrder.preorderTraversal(root);         preOrder.preorder2(root);     }       /**      * 迭代算法      *      * @param root      * @return      */     public List preorder2(TreeNode root) {         List list = new ArrayList();         if (root == null) {             return list;         }         LinkedList stack = new LinkedList();         TreeNode prev = null;         while (root != null || !stack.isEmpty()) {             while (root != null) {                 stack.addLast(root);                 root = root.left;             }             root = stack.removeLast();             if(root.right == null || root.right == prev){                 // 根节点                 list.add(root.val);                 prev = root;                 root = null;             } else {                 stack.addLast(root);                 root = root.right;             }         }          System.out.println(list);         return list;     }       /**      * 递归      *      * @param root      * @return      */     public List preorderTraversal(TreeNode root) {         List list = new ArrayList();          order(root, list);         System.out.println(list);         return list;     }      private void order(TreeNode root, List list) {         if (root == null) {             return;         }         if (root.left != null) {             order(root.left, list);         }         if (root.right != null) {             order(root.right, list);         }         list.add(root.val);     }   }二叉树前中后序遍历，两种方法的复杂度时间复杂度：O(n)空间复杂度：O(n)
　　好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！