144.二叉树的前序遍历
题目链接
前、中、后的遍历的递归做法实际上都是一样的，区别就是遍历操作的位置不同。
对于先序遍历，也就是先根，即把查看当前结点的操作放在最前面即可。
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();preorder(root,res);return res;}public void preorder(TreeNode root, List<Integer> result) {if (root == null) {return;}result.add(root.val);preorder(root.left, result);preorder(root.right, result);}
}
而中序和后序遍历也是一样：
// 中序
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();midorder(root,res);return res;}public void midorder(TreeNode root, List<Integer> res){if(root == null){return;}midorder(root.left,res);res.add(root.val);midorder(root.right,res);}
}
//后序
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();postorder(root,res);return res;}public void postorder(TreeNode root, List<Integer> res){if(root == null){return;}postorder(root.left,res);postorder(root.right,res);res.add(root.val);}
}
python版本也一样，这里就写一种：
class Solution:def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []def dfs(root):if root is None:return dfs(root.left)dfs(root.right)res.append(root.val)dfs(root) # 调用dfs函数开始遍历return res
如果不用递归，那会有一点麻烦，但也仅仅是代码上的。因为递归本身就是借用系统栈，而使用迭代则是自己创建栈进行操作即可。
前序则是将根节点入栈，后续的结点是按照先右边再左边的顺序入栈（因为我们要先处理左子，因此左子后入栈可以先被pop）。
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null){return res;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode tmp = stack.pop();res.add(tmp.val);if(tmp.right != null){stack.push(tmp.right);}if(tmp.left != null){stack.push(tmp.left);}}return res;}
}
但中后序的操作和前序不太一样（虽然有方法可以进行统一，但本文不赘述）。而后序则是将先序（根左右）进行操作（根左右->根右左->左右根），即调整处理顺序+反转数组。
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()){if (cur != null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();result.add(cur.val);cur = cur.right;}}return result;}
}
102 二叉树的层序遍历
题目链接
层序遍历用的是队列，每次将一个节点入队，处理完当前节点，则其子节点分别入队，下一轮再处理子节点，也就是下一层的内容。
例如，一棵树为1、2、3、4、5（数组表示），那么第一次是1入队，处理完1后，1的子节点也就是2、3入队。处理完2，也就是2的子节点入队，即4、5。3处理后没有子节点，就剩下4、5需要处理。
如果是要求返回的是一个列表，没有嵌套结构，那就会好做很多，我们就按照上面的流程构造队列然后不断处理即可。但现在返回的要求是每一层都要有一个单独的列表，因此就麻烦一些。
我们就使用两重循环，第一重是记录队列是否为空，第二重则是看当前遍历的层。
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<TreeNode> deque = new LinkedList<>();List<List<Integer>> res = new ArrayList<List<Integer>>();if(root == null){return res;}deque.add(root);while(!deque.isEmpty()){// len记录当前层的个数，tmpList则是存放当前层，最后统一add到res上int len = deque.size();List<Integer> tmpList = new ArrayList<>();while(len>0){TreeNode tmpNode = deque.removeFirst();tmpList.add(tmpNode.val);if(tmpNode.left!=null){deque.add(tmpNode.left);}if(tmpNode.right!=null){deque.add(tmpNode.right);}len--;}res.add(tmpList);}return res;}
}
python版本如下：
class Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root:return []res = []deque = [root]while(len(deque)!=0):size = len(deque)tempList = []for i in range(size):tmp = deque.pop(0)if tmp.left is not None:deque.append(tmp.left)if tmp.right is not None:deque.append(tmp.right)tempList.append(tmp.val)res.append(tempList)return res
所以层序遍历大致就是如下的步骤：将节点入队列，然后对队列进行操作：队头元素出队进行操作，将队头元素的子节点放入队列。如果遇到返回列表要用嵌套列表，就单独申请一个tmpList进行存储。
下面的题都是基于层序遍历的：
107 二叉树的层次遍历2
题目描述
没啥可说的，把最后结果逆转即可。
List<List<Integer>> result = new ArrayList<>();for (int i = list.size() - 1; i >= 0; i-- ) {result.add(list.get(i));}return result;
或者
return result[::-1]
199 二叉树的右视图
题目链接
我起初单纯的以为只要看右子树就可以了，但忽略了一个问题：
如果一棵树只有左子树没有右子树，从右边看看到的也是左子树，因此不能单纯的这样考虑。
仔细思考一下，还是用层序遍历的思想更简单，只需要考虑层序的最后一个元素是谁就可以了。因此代码如下：
class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();if(root==null){return res;}List<TreeNode> deque = new LinkedList<>();deque.add(root);while(!deque.isEmpty()){int len = deque.size();List<Integer> tmpList = new LinkedList<>();// 得到当前层的内容while(len>0){TreeNode tmpNode = deque.removeFirst();tmpList.add(tmpNode.val);if(tmpNode.left != null){deque.add(tmpNode.left);}if(tmpNode.right!=null){deque.add(tmpNode.right);}len--;}// 选择当前层最后的一个元素res.add(tmpList.removeLast());}return res;}
}
637.二叉树的层平均值
题目链接
很简单，简单的层序遍历记录大小，最后计算平均值即可。注意用浮点数。
*/
class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> res = new ArrayList<>();List<TreeNode> deque = new LinkedList<>();deque.add(root);while(!deque.isEmpty()){Double avg=0.0;int len = deque.size();for(int i=0; i<len; i++){TreeNode tmpNode = deque.removeFirst();avg += tmpNode.val;if(tmpNode.left != null){deque.add(tmpNode.left);}if(tmpNode.right!=null){deque.add(tmpNode.right);}}res.add(avg/len);}return res;}
}
429 n叉树的层序遍历
题目链接
主要是n叉树的子节点不能直接用if判断，而是用for来判断即可。
class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> res = new ArrayList<List<Integer>>();List<Node> deque = new LinkedList<>();if(root==null){return res;}deque.add(root);while(!deque.isEmpty()){//tmpList记录这一层的节点值List<Integer> tmpList = new ArrayList<>();int len = deque.size();// 得到一层的节点while(len>0){Node tmpNode = deque.removeFirst();tmpList.add(tmpNode.val);//children用来遍历全部的子节点，将子节点添加进入队列。List<Node> children = tmpNode.children;for(Node child :children){deque.add(child);}len--;}// 将一层的节点值添加进resres.add(tmpList);}return res;}
}
515. 在每个树行中找最大值
题目描述
很简单，找最大值即可
class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> res = new ArrayList<>();List<TreeNode> deque = new LinkedList<>();if(root==null){return res;}deque.add(root);while(!deque.isEmpty()){int len = deque.size();int max = Integer.MIN_VALUE;for(int i=0; i<len; i++){TreeNode node = deque.removeFirst();max =Math.max(node.val,max);if(node.left!=null){deque.add(node.left);}if(node.right!=null){deque.add(node.right);}}res.add(max);}return res;}
}
116. 填充每个节点的下一个右侧节点指针
题目链接
使用queue实现linkedList接口，更改指针的操作只需要当前节点的next指向队列的顶端即可。因为原先队列的队头元素移出，该元素指向的就是移除元素后的队头元素。
class Solution {public Node connect(Node root) {if (root == null) {return root;}// 初始化队列，将根节点入队Queue<Node> queue = new LinkedList<>();queue.add(root);// 循环处理队列中的每一层节点while (!queue.isEmpty()) {int size = queue.size();// 遍历当前层的所有节点for (int i = 0; i < size; i++) {Node node = queue.poll();// 如果当前节点不是本层最后一个节点，连接 next 指针到下一个节点if (i < size - 1) {node.next = queue.peek();} else {node.next = null;}// 将当前节点的子节点入队if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}}return root;}
}
104. 二叉树的最大深度
题目描述
很简单，只是深度优先遍历，直接用递归解决即可。
class Solution {int max = 0; public int maxDepth(TreeNode root) {if (root == null) {return 0;}dfs(1, root);return max;}public void dfs(int depth, TreeNode node){max = Math.max(max,depth);if(node.left!=null){dfs(depth+1, node.left);}if(node.right!=null){dfs(depth+1, node.right);}}
}
//或者这样
class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;} else {int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.max(leftHeight, rightHeight) + 1;}}
}
python版本：
class Solution:def maxDepth(self, root):if root is None: return 0 else: left_height = self.maxDepth(root.left) right_height = self.maxDepth(root.right) return max(left_height, right_height) + 1
111. 二叉树的最小深度
题目描述
最小深度元也是一样，不过深度的大小一定是遍历到叶子节点才能知道，也就是要没左右子节点才可以，因此设置一个flag。
class Solution {int min = 100005;public int minDepth(TreeNode root) {if(root==null){return 0;}else{dfs(root,1);}return min;}public void dfs(TreeNode node,int depth){int flag=0;if(node.left!=null){dfs(node.left,depth+1);flag=1;}if(node.right!=null){dfs(node.right,depth+1);flag=1;}if(flag==0){min = Math.min(min,depth);} }
}
python版本：
class Solution:Min = 100005def dfs(self, node, depth):if node.left is None and node.right is None:self.Min = min(self.Min, depth)if node.left is not None:self.dfs(node.left, depth + 1)if node.right is not None:self.dfs(node.right, depth + 1)def minDepth(self, root: Optional[TreeNode]) -> int:if root is None:return 0else:self.dfs(root, 1)return self.Min
226. 翻转二叉树
题目描述
很简单，直接进行反转即可，用reverse不断的进行反转。也可以写在一个函数里。
class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return root;}reverse(root);return root;}public void reverse(TreeNode node){if (node == null) {return;}TreeNode tmp = node.left;node.left = node.right;node.right = tmp;reverse(node.left);reverse(node.right);}
}
//或者这样
class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);root.left = right;root.right = left;return root;}
}
python版本：
class Solution:def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root:return rootleft = self.invertTree(root.left)right = self.invertTree(root.right)root.left, root.right = right, leftreturn root
