算法练习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;
       }
   }