每日算法2024/08/12
题目一：144. 二叉树的前序遍历❤
题目思路
看注释
题解代码
// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();preorder(root, result); // 前序遍历return result;}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> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop(); // 中result.add(node.val);if (node.right != null){stack.push(node.right); // 右（空节点不入栈）}if (node.left != null){stack.push(node.left); // 左（空节点不入栈）}}return result;}
}// 前序遍历迭代方式二
class Solution {public static void preOrder(TreeNode root) {List<Integer> result = new ArrayList<>();//定义一个变量，存放当前节点TreeNode curr = root;//定义一个栈数据结构，用来存放遍历过程中的节点LinkedList<TreeNode> stack = new LinkedList<>();//当前孩子不为空或者栈中不为空，则循环while (curr != null || !stack.isEmpty()) {if (curr != null) {//如果当前节点不为空,打印result.add(curr.val);//打印后将该节点放入栈中stack.push(curr);//将curr指向当前节点的左孩子curr = curr.left;} else {//如果当前节点为空，则从栈中弹出节点TreeNode pop = stack.pop();//将curr指向弹出节点的右孩子（此时当前节点的所有左孩子和当前节点以及全部打印）curr = pop.right;}}}
}题目二：94. 二叉树的中序遍历❤
题目思路
如上
题解代码
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}void inorder(TreeNode root, List<Integer> list) {if (root == null) {return;}inorder(root.left, list);list.add(root.val); // 注意这一句inorder(root.right, list);}
} /*** 中序遍历——迭代*/
public static void inOrder(TreeNode root) {List<Integer> inOrder = new LinkedList<>();//先定义一个变量存放当前节点TreeNode curr = root;//定义一个栈数据结构，用来存放遍历过程中的节点LinkedList<TreeNode> stack = new LinkedList<>();//当左孩子不为空或者栈中不为空，则循环while (curr != null || !stack.isEmpty()) {if (curr != null) {//如果当前节点不为空，将其放入栈中stack.push(curr);//将curr指向当前节点的左孩子curr = curr.left;} else {//如果当前节点为空了，则从栈中弹出节点并输出（说明被弹栈节点左孩子为空）TreeNode pop = stack.pop();inOrder.add(pop.val);//将curr指向当前节点的右孩子curr = pop.right;}}
}题目三：145. 二叉树的后序遍历❤
题目思路
如上
后序遍历的迭代代码需要注意如下：
-
如果遍历到的节点为null时，不要急着将栈顶元素弹出，先通过peek方法获取到栈顶元素，判断栈顶元素的右孩子是否为null，或者右孩子是否已经被处理过（如何判断右孩子已经被处理？如果遍历到的节点的右孩子等于上一次被弹栈的元素，则说明右孩子已经被处理，因此后序遍历需要额外定义一个指针指向上一次被弹栈的节点），如果为null或者已经被处理，此时才弹出栈顶元素，如果没有，则需要先处理右孩子！！！
题解代码
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();postorder(root, res);return res;}void postorder(TreeNode root, List<Integer> list) {if (root == null) {return;}postorder(root.left, list);postorder(root.right, list);list.add(root.val); // 注意这一句}
}/*** 后序遍历*/
public static void postOrder(TreeNode root) {List<Integer> postOrder = new LinkedList<>();//先定义一个变量存放当前节点TreeNode curr = root;//定义一个栈数据结构，用来存放遍历过程中的节点LinkedList<TreeNode> stack = new LinkedList<>();//定义一个变量pop存放最近从栈中弹出的节点TreeNode pop = null;//当左孩子不为空或者栈中不为空，则循环while (curr != null || !stack.isEmpty()) {if (curr != null) {//如果当前节点不为空，将其放入栈中stack.push(curr);//将curr指向当前节点的左孩子curr = curr.left;} else {//后序遍历调用栈数据结构的peek方法，先操作栈顶元素，不急着弹出TreeNode peek = stack.peek();//如果栈顶节点的右孩子为空，或者与最近弹出栈的节点相同if (peek.right == null || peek.right == pop) {//则将栈顶元素弹出并打印pop = stack.pop();postOrder.add(pop.val);} else {//如果不是，则将curr指向栈顶元素的右孩子curr = peek.right;}}}
}题目四：102. 二叉树的层序遍历❤
题目思路
看注释
题解代码
// 二叉树层序遍历-定义变量记录每层节点个数
public List<List<Integer>> levelOrder(TreeNode root) {// 存储结果List<List<Integer>> result = new ArrayList<>();// 如果根节点为空，则直接返回结果if (root == null) {return result;}// 创建一个队列Queue<TreeNode> queue = new LinkedList<>();// 将根节点放入队列queue.offer(root);// 记录每一层的节点个数int c1 = 1;//每一层节点个数// 当队列不为空时while (!queue.isEmpty()) {// 记录下一层节点个数int c2 = 0;//下一层节点个数// 创建一个存储每一层节点的列表List<Integer> lever = new ArrayList<>();// 遍历每一层节点for (int i = 0; i < c1; i++) {// 从队列中取出一个节点TreeNode node = queue.poll();// 将节点的值添加到列表中lever.add(node.val);// 如果该节点有左子节点，则将左子节点放入队列if (node.left != null) {queue.offer(node.left);c2++;}// 如果该节点有右子节点，则将右子节点放入队列if (node.right != null) {queue.offer(node.right);c2++;}}// 更新每一层节点个数c1 = c2;// 将每一层节点列表添加到结果中result.add(lever);}// 返回结果return result;
}// 二叉树层序遍历-使用队列长度表示每层节点个数
public int maxDepth(TreeNode root) {if (root == null) {return 0;}//二叉树的层序遍历需要用到队列数据结构Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);//记录深度int depth = 0;while (!queue.isEmpty()) {//每一层节点个数<队列中元素个数记录的就是每一层节点的个数>int size = queue.size();//当前层有多少节点就循环多少次for (int i = 0; i < size; i++) {//就把多少节点从队列中弹出，并把它们的孩子加入队列TreeNode pollNode = queue.poll();if (pollNode.left != null) {queue.offer(pollNode.left);}if (pollNode.right != null) {queue.offer(pollNode.right);}}//每循环一层，层数 + 1depth++;}//当循环完所有节点，返回层数return depth;
}题目五：107. 二叉树的层序遍历 II
题目思路
注释
题解代码
/*正常的层序遍历，只不过先将每一层遍历到的元素加入栈中最后将栈中的元素弹栈再加入结果集中，实现反转*/
public List<List<Integer>> levelOrderBottom(TreeNode root) {// 结果集List<List<Integer>> res = new ArrayList<>();// 栈Stack<List<Integer>> result = new Stack<>();if (root == null) {return res;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> level = new ArrayList<>();int size = queue.size();for (int i = 0; i < size; i++) {TreeNode polled = queue.poll();level.add(polled.val);if (polled.left != null) {queue.offer(polled.left);}if (polled.right != null) {queue.offer(polled.right);}}// 入栈result.push(level);}// 将栈中的元素弹栈加入结果集合while (!result.isEmpty()) {res.add(result.pop());}return res;
}/*正常的层序遍历，在加入每一层的元素到结果集时，始终加入到结果集的链表头 res.add(0, level);*/
public List<List<Integer>> levelOrderBottom2(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) {return res;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> level = new ArrayList<>();// 使用队列长度表示每层节点的节点个数int size = queue.size();for (int i = 0; i < size; i++) {TreeNode polled = queue.poll();level.add(polled.val);if (polled.left != null) {queue.offer(polled.left);}if (polled.right != null) {queue.offer(polled.right);}}// 将每层的元素集合始终加入结果集的链表头res.add(0, level);}return res;
}