算法练习0212

1、二叉树层次遍历 

解体思路：

1. 使用队列（Queue）：我们可以使用一个队列来帮助我们访问节点。队列确保我们按照广度优先的顺序访问节点。

2. 初始化：将根节点加入到队列中。如果根节点是空，直接返回空列表。

3. 逐层遍历：

   • 在每一层中，我们记录当前层的节点数量（即队列的大小）。
   • 处理当前层的每个节点，将其值添加到结果列表中。
   • 对于每个节点，将它的左子节点和右子节点（如果存在）添加到队列中。

4. 结束条件：当队列为空时，表示遍历已完成

5. 代码

   /*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
   class Solution {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); while (!queue.isEmpty()) {int levelSize = queue.size();List<Integer> currentLevel = new ArrayList<>();for (int i = 0; i < levelSize; i++) {TreeNode currentNode = queue.poll();currentLevel.add(currentNode.val); if (currentNode.left != null) {queue.offer(currentNode.left);}if (currentNode.right != null) {queue.offer(currentNode.right);}}result.add(currentLevel); // 将当前层的列表加入结果}return result; // 返回最终的结果}
   }

2、两数相加 

解题思路

1. 理解链表存储：由于数字是逆序存储的，因此链表的头节点为最低位。
2. 逐位相加：从链表的头节点开始逐位相加，并处理进位（carry）。
3. 构建新链表：
   • 创建一个新的链表，用于存储结果。
   • 使用一个指针（current）来帮助我们构建新链表，同时用一个 dummyHead 节点简化链表操作。
4. 处理进位：
   • 如果两边链表的数字相加超过 9，则需要向高位进位。
   • 尽管有链表的节点值未处理完，但在所有节点都处理完后，可能仍然有进位需要添加。

具体步骤：

1、初始化一个 dummyHead 节点和一个指针 current 指向该节点，开始时进位 carry 为 0。

2、当链表 l1 或 l2 或进位 carry 不为 0 时，循环处理每一位。

3、计算当前位的两个值 val1 和 val2，如果链表已遍历完则使用 0 作为值。

4、计算当前位的和：total = val1 + val2 + carry，并更新 carry。

5、将当前位的结果附加到新链表中，并将 current 指向新节点。

6、移动到下一个节点。

7、结束时返回 dummyHead.next，即新链表的头节点

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummyHead = new ListNode(0); ListNode current = dummyHead;          int carry = 0;                          while (l1 != null || l2 != null || carry != 0) {int val1 = (l1 != null) ? l1.val : 0; int val2 = (l2 != null) ? l2.val : 0; // 计算当前位的和int total = val1 + val2 + carry;carry = total / 10;                   current.next = new ListNode(total % 10); // 移动到下一个节点current = current.next;if (l1 != null) l1 = l1.next;if (l2 != null) l2 = l2.next;}return dummyHead.next; }
}

3、二叉树的层平均值 

解题思路：
1、利用队列进行层次遍历
2、记录下每一层的数据，然后计算每一层的平均值
代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> result = new ArrayList<>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int levelSize = queue.size(); double sum = 0;for (int i = 0; i < levelSize; i++) {TreeNode currentNode = queue.poll();sum += currentNode.val; if (currentNode.left != null) {queue.offer(currentNode.left);}if (currentNode.right != null) {queue.offer(currentNode.right);}}result.add(sum / levelSize);}return result; }
}

4、将有序数组转换为二叉搜索树 

 

解题思路：

1. 递归函数：编写一个递归函数，它接受数组的开始和结束索引。函数的主要任务是找到中间索引并建立树的节点。
2. 选择中间元素：找到当前范围内的中间元素，将其作为根节点。对于偶数个元素，可以选择左中间元素。
3. 递归构建左子树和右子树：使用左半部分和右半部分的索引递归调用该函数，以构建左子树和右子树。
4. 返回树的根节点：递归结束后，返回当前子树的根节点。
   代码：

   /*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
   class Solution {public TreeNode sortedArrayToBST(int[] nums) {return buildTree(nums, 0, nums.length - 1);}private TreeNode buildTree(int[] nums, int left, int right) {if (left > right) {return null;}int mid = left + (right - left) / 2;TreeNode node = new TreeNode(nums[mid]); node.left = buildTree(nums, left, mid - 1); node.right = buildTree(nums, mid + 1, right);   return node; }
   }

4、LCR 144. 翻转二叉树 

解题思路：

1. 基线条件：如果当前节点为空（即根节点是 null），则返回 null。
2. 递归处理：
   • 先递归调用 flipTree 处理左子树和右子树。
   • 然后交换当前节点的左右子节点。
3. 返回翻转后的树的根节点。

   /*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
   class Solution {public TreeNode flipTree(TreeNode root) {if (root == null) {return null;}TreeNode left = flipTree(root.left);TreeNode right = flipTree(root.right);root.left = right;root.right = left;return root;}
   }