LeetCode算法之--二叉树系列

点赞收藏，以防遗忘

本文【程序大视界】已收录，关注免费领取互联网大厂学习资料，添加博主好友进群学习交流，欢迎留言和评论，一起交流共同进步。

【一】前言

二叉树也是面试算法的常见题型，通常程序会自定义树节点，需要我们实现如找出深度、遍历等。

【二】二叉树的最大深度

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 ;}
}

【三】二叉树的遍历

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());}}
}