二叉树是一种基础数据结构，在算法面试中是常客，也是众多数据结构的基石
今日任务：
- 递归遍历
- 迭代遍历
- 统一遍历
关于二叉树的遍历方式我最喜欢用的是层序遍历，今天讲解主要讲解几种比较基础的遍历方式，二叉树的遍历也分为前中后序遍历，具体区别如图所示
网络异常，图片无法展示
|
图片来自于代码随想录网站
递归遍历
递归算法三要素:确定递归函数的参数和返回值确定终止条件确定单层递归的逻辑
代码展示
// 前序遍历·递归·LC144_二叉树的前序遍历 class Solution { public static List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); if (root == null){ return list; } getTreeVal(root,list); return list; } public static void getTreeVal(TreeNode tree, List<Integer> list){ list.add(tree.val); if (tree.left != null){ getTreeVal(tree.left,list); } if (tree.right != null){ getTreeVal(tree.right, list); } } } // 中序遍历·递归·LC94_二叉树的中序遍历 class Solution { public static List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); getValue(root, result); return result; } public static void getValue(TreeNode tree, List<Integer> list){ if (tree == null){ return; } getValue(tree.left, list); list.add(tree.val); getValue(tree.right,list); } } // 后序遍历·递归·LC145_二叉树的后序遍历 class Solution { public static List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); getTreeVal(root,list); return list; } public static void getTreeVal(TreeNode tree, List<Integer> list){ if (tree == null){ return; } getTreeVal(tree.left, list); getTreeVal(tree.right,list); list.add(tree.val); } } 复制代码
统一迭代法
代码展示
以下为前序遍历代码，中序和后序的代码仅仅更改 if (node != null) 里面栈的进入顺序即可
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<>(); Stack<TreeNode> st = new Stack<>(); if (root != null) st.push(root); while (!st.empty()) { TreeNode node = st.peek(); if (node != null) { st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中 if (node.right!=null) st.push(node.right); // 添加右节点（空节点不入栈） if (node.left!=null) st.push(node.left); // 添加左节点（空节点不入栈） st.push(node); // 添加中节点 st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。 } else { // 只有遇到空节点的时候，才将下一个节点放进结果集 st.pop(); // 将空节点弹出 node = st.peek(); // 重新取出栈中元素 st.pop(); result.add(node.val); // 加入到结果集 } } return result; } } 复制代码
总结
这边只写了递归排序和统一迭代法，迭代排序也很简单，感兴趣的可以了解一下，我还是比较喜欢层序遍历的方式
