01前言
很多伙伴大学的时候就学过二叉树的数据结构以及相关遍历的算法（没有学过的伙伴可以先百度学习了解一下二叉树的数据结构知识）最简单的如：前序遍历、中序遍历、后序遍历。而树这种数据结构跟其他的数据结构不太一样，稍微复杂而且抽象在解题的时候最好手画草图，把抽象的结构形象化可以提高理解度加快解题。二叉树也是面试算法的常见题型，通常程序会自定义树节点，需要我们实现如找出深度、遍历等。即使我们记得树的前中后序遍历顺序，但是要用代码来实现它却并非易事，它的难度体现在抽象、如何选择合适的数据结构等。
02二叉树的最大深度
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
【解法一】深度优先：新建一个result集合用于保存并返回结果集合，边界条件为root为null，则返回result，递归方法开始传入root和levle为0层，依次递增层数并新建结果集合里的子集list，结果集合中添加该节点的值val，并递归遍历该节点的左子树和右子树，直至递归遍历完该二叉树的所有节点，返回的result结果集合就是所求。
class Solution { List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<List<Integer>> levelOrder(TreeNode root) { If(root == null){ return result ; } dfs(root,0); return result; } public void dfs(TreeNode root,int level){ //递归终止条件 If(root == null){ return ; } If( result.size == level){ result.add(New ArrayList<Integer>()); } result.get(level).add(root.val); dfs(root.right,level+1); dfs(root.right,level+1); }}
【解法二】广度优先：新建一个result集合用于保存和返回结果集合，边界条件当root为空，则直接返回结果集。建队列queue保存root根节点，按照每一层左、右子树的顺序，一次访问二叉树的节点，遍历每一层的节点时用一个list集合把该层的所有节点从左到右顺序保存起来，遍历完每一层把list集合添加到结果集合中，遍历完所有层，result结果集合就是要求的答案。
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<List<Integer>>(); If(root == null){ return result ; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); While(!queue.isEmpty()){ Int size = queue.size(); List<Integer> list = new ArrayList<Integer>(); While(size >0){ TreeNode node = queue.poll(); list .add(node.val); If(node.left != null){ queue.offer(node.left); } If(node.right != null){ queue.offer(node.right); } size --; } result.add(list); } return result ; }}
03二叉树的遍历
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]输出：[1,3,2]示例 2：
输入：root = []输出：[]示例 3：
输入：root = [1]输出：[1]提示：
树中节点数目在范围 [0, 100] 内-100 <= Node.val <= 100进阶: 递归算法很简单，你可以通过迭代算法完成吗？
【解法一】迭代解决：新建一个List集合用以存放结果返回集合，新建一个Deque双端队列用作遍历二叉树出入栈使用，当root或stack不为空时，遍历二叉树，一直遍历到左子树为空时，从栈弹出节点并把弹出节点的值存入栈中，指针指向弹出节点的右子树节点，继续遍历访问弹出节点右子树节点是否为空，重复该步骤直至遍历完该二叉树为止。
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> dataList = new ArrayList<Integer>(); Deque<TreeNode> stack = new LinkedList<TreeNode>(); While(root != null || !stack.isEmpty()){ If(root!= null){ stack.push(root); root = root.left; }else{ root = stack.pop(); dataList.add(root.val); root = root.right; } } return dataList ; }}
【解法二】递归：递归的解法很简单，递归循环左节点和右节点，递归的终止条件是当root为空时返回。
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> dataList = new ArrayList<Integer>(); Inorder(root,dataList ); return dataList ; } public void inorder(TreeNode root,List<Integer> dataList){ If(root == null){ return; } inorder(root.left,dataList); dataList.add(root.val); inorder(root.right,dataList); }}
二叉树的前序遍历
【迭代解决】前序遍历的出入栈顺序是：先根节点入栈，根节点出栈，再右节点入栈、左节点入栈，左节点出栈、右节点入栈；如此往复循环直至遍历完整颗二叉树，在每一次出栈时保存节点的值放入list链表，最后得到的list结果集合就是所求结果。
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> dataList = new ArrayList<Integer>(); Deque<TreeNode> stack = new LinkedList<TreeNode>(); stack.push(root); While( !stack.isEmpty()){ root = stack.pop(); dataList.add(root.val); //先压入右节点，弹出顺序刚好相反 If(root.right != null){ stack.push(root.right ); } //再压入左节点，弹出顺序刚好相反 If(root.left!= null){ stack.push(root.left); } } return dataList ; }}
【后序遍历】后序遍历的顺序是：左节点-->右节点-->根 而出栈和入栈的顺序则刚好相反，这题的关键是需要用两个栈结构来解答，一个栈用来遍历，另一个栈用来存储，遍历完第一个栈后，第二个栈出栈遍历的结构就是后续遍历。
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> dataList = new ArrayList<Integer>(); //第一个栈用来遍历二叉树 Deque<TreeNode> stack1 = new LinkedList<TreeNode>(); stack1.push(root); //第二个栈用来存放节点最终遍历出栈的顺序就是所要求结果 Deque<TreeNode> stack2 = new LinkedList<TreeNode>(); While(!stack1.isEmpty()){ root = stack1.pop(); stack2.push(root.val); If(root.left != null){ stack1.push(root.left); } If(root.right != null){ stack1.push(root.right); } } while(!stack2.isEmpty()){ dataList.add(stack2.pop()); } }}
04总结
关于二叉树的解法，常见为深度优先遍历和广度优先遍历，深度优先一般选用递归解法，如求二叉树的深度、层序遍历（节点从左到右顺序）、中序遍历、反转二叉树、对称二叉树等，广度优先采用Queue队列、Deque栈的数据结构来求解，一层一层的遍历按照要求实现具体解法，广度优先也称为迭代解法。
![[leetcode~dfs]1261. 在受污染的二叉树中查找元素](https://ucc.alicdn.com/pic/developer-ecology/okfcmqqjwxoec_335a965e888346009ec98ec28a431196.png?x-oss-process=image/resize,h_160,m_lfit)