当前位置：首页 > article >正文

算法练习0212

article 2025/2/14 0:07:39

1、二叉树层次遍历

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

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

逐层遍历：

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

结束条件：当队列为空时，表示遍历已完成
代码
/**
 * 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、两数相加

解题思路

理解链表存储：由于数字是逆序存储的，因此链表的头节点为最低位。
逐位相加：从链表的头节点开始逐位相加，并处理进位（carry）。
构建新链表：
创建一个新的链表，用于存储结果。
使用一个指针（current）来帮助我们构建新链表，同时用一个 dummyHead 节点简化链表操作。

处理进位：
如果两边链表的数字相加超过 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、将有序数组转换为二叉搜索树

解题思路：
递归函数：编写一个递归函数，它接受数组的开始和结束索引。函数的主要任务是找到中间索引并建立树的节点。
选择中间元素：找到当前范围内的中间元素，将其作为根节点。对于偶数个元素，可以选择左中间元素。
递归构建左子树和右子树：使用左半部分和右半部分的索引递归调用该函数，以构建左子树和右子树。
返回树的根节点：递归结束后，返回当前子树的根节点。
代码：
/**
 * 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. 翻转二叉树

解题思路：

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

返回翻转后的树的根节点。

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