树：数据结构解析

前言

树是一种非线性的数据结构，由节点（node）和边（edge）组成。它是一种层次结构，具有一个根节点，每个节点可以有多个子节点。

树的主要特点包括：

1. 根节点：树唯一的起始节点。
2. 子节点：每个节点可以有任意数量的子节点。
3. 父节点：一个节点的直接上级节点称为其父节点。
4. 叶子节点：没有子节点的节点称为叶子节点或终端节点。
5. 兄弟节点：具有相同父节点的节点称为兄弟节点。
6. 子树：以某个节点为根节点，由该节点及其所有子节点组成的树称为子树。
7. 深度（Depth）：根节点到某个节点的唯一路径的长度称为该节点的深度。
8. 高度（Height）：根节点到叶子节点的最长路径长度称为树的高度。
9. 路径（Path）：由边相连的节点序列构成一条路径。
10. 祖先节点（Ancestor）：沿着路径从根节点到某个节点的所有节点称为该节点的祖先节点。
11. 子孙节点（Descendant）：某个节点的所有后代节点称为其子孙节点。

树的应用广泛，常见的应用场景包括文件系统、组织结构、数据库索引等。树的各种变种，如二叉树、平衡树、红黑树等，都是在树的基础上进行了特殊的限制或优化，以满足不同的需求。
相同的树

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 boolean isSameTree(TreeNode p , TreeNode q){
		if(p == null && q == null){
			return true;
			
		}
		if(p!=null && q !=null && p.val == q.val){
			return isSameTree(p.left,q.left) &&isSameTree(p.right,q.right);
		}else{
			return false;
		}
	}
}

两两交换链表中的节点

public class listNode{
	int val ;
	ListNode next;
	ListNode(int x){
		val =x;
	}
}
class Solution{
	public ListNode swapPairs(ListNode head){
		ListNode list1 = new ListNode(0);
		list1.next = head;
		ListNode list2 = list1;
		while(head !=null && head.next != null ){
			list2.next =head.next;
			head.next = list2.next.next;
			list2.next.next = head;
			list2 = list2.next.next;
			head = list2.next;
		}
		return list1.next;
	}
}

这段代码展示了一个解决方案，用于交换给定链表中节点的成对元素。具体来说，给定一个链表 1 -> 2 -> 3 -> 4，经过这个方法处理后，链表变为 2 -> 1 -> 4 -> 3。如果链表的长度是奇数，那么最后一个节点不会被交换。

代码分析

ListNode类定义

首先，定义了一个 ListNode 类，用于表示链表中的节点。每个节点包含一个整数值 val 和指向下一个节点的引用 next。构造器接受一个整数参数 x 并将其赋值给节点的值。

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

解决方案类

接着，在 Solution 类中定义了一个名为 swapPairs 的方法，该方法接收一个 ListNode 类型的参数 head，表示链表的头节点，并返回修改后的链表头节点。

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 创建一个伪头节点，简化边界条件处理
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // 初始化一个指针，指向伪头节点
        ListNode prev = dummy;
        
        // 当前节点
        while (head != null && head.next != null) {
            // 下一个节点
            prev.next = head.next;
            
            // 移动当前节点到下一个节点之后
            head.next = prev.next.next;
            
            // 更新下一个节点的下一个指针
            prev.next.next = head;
            
            // 移动prev和head指针
            prev = prev.next.next;
            head = prev.next;
        }
        
        // 返回新的头节点
        return dummy.next;
    }
}

逻辑解析

1. 初始化：创建一个虚拟头节点 dummy，并让 dummy.next 指向原链表的头节点 head。这样做可以简化边界情况的处理，比如处理原链表为空或只有一个节点的情况。

2. 循环条件：while 循环会一直执行，直到当前节点 head 或其下一个节点 head.next 为空。这意味着只要还有至少两个节点可以交换，循环就会继续。

3. 交换逻辑：

   • prev.next = head.next;：将当前节点的下一个节点作为新的起始节点。
   • head.next = prev.next.next;：将当前节点的下一个指针指向再下一个节点，完成交换的第一步。
   • prev.next.next = head;：将交换后的节点指回原来的当前节点，完成交换的第二步。

4. 移动指针：

   • prev = prev.next.next;：将 prev 指针向前移动两次，准备下一次交换。
   • head = prev.next;：将 head 指针向前移动一次，指向下一个待交换的节点。

5. 返回结果：最终返回 dummy.next，即新的链表头节点。

这种方法的时间复杂度为 O(n)，其中 n 是链表中的节点数量，因为每个节点都会被访问一次。空间复杂度为 O(1)，因为除了几个指针变量外，没有使用额外的空间。
进阶：在不修改链节点，仅修改节点本身

如果我们希望在不改变链表节点的情况下，只通过修改节点的指针来交换相邻节点的位置，那么我们需要调整交换逻辑。具体来说，我们要在原地交换相邻节点的 next 指针，而不是创建新的节点。

进阶版本的代码实现

下面是一个进阶版本的代码实现，它不创建新的节点，而是通过修改现有节点的 next 指针来达到交换相邻节点的效果。

public class Solution {
    public ListNode swapPairs(ListNode head) {
        // 如果链表为空或只有一个节点，直接返回
        if (head == null || head.next == null) {
            return head;
        }

        // 初始化一个虚拟头节点，简化边界条件处理
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode curr = head;

        // 当前节点及其下一个节点都不为空时进行交换
        while (curr != null && curr.next != null) {
            ListNode first = curr;  // 当前节点
            ListNode second = curr.next;  // 下一个节点
            
            // 调整指针
            prev.next = second;     // 虚拟头节点指向下一个节点
            first.next = second.next;  // 当前节点指向下一个节点的下一个节点
            second.next = first;    // 下一个节点指向当前节点

            // 移动prev和curr指针
            prev = first;
            curr = first.next;
        }

        // 返回新的头节点
        return dummy.next;
    }
}

代码解析

1. 初始化：首先检查链表是否为空或只有一个节点，如果是，则直接返回头节点。
2. 虚拟头节点：创建一个虚拟头节点 dummy，并让 dummy.next 指向原链表的头节点 head。这样可以简化处理边界条件。
3. 交换逻辑：
   • 定义 first 和 second 分别指向当前节点和它的下一个节点。
   • 修改指针使 prev.next 指向 second。
   • 修改 first 的 next 指向 second 的下一个节点。
   • 修改 second 的 next 指向 first。
4. 移动指针：更新 prev 和 curr 指针以便进行下一轮交换。
5. 返回新头节点：返回 dummy.next 作为新的头节点。

举例说明

假设我们有如下链表：1 -> 2 -> 3 -> 4。

• 初始状态：dummy -> 1 -> 2 -> 3 -> 4
• 第一次交换后：dummy -> 2 -> 1 -> 3 -> 4
• 第二次交换后：dummy -> 2 -> 1 -> 4 -> 3

通过这种方式，我们可以在不改变节点自身的情况下，通过改变节点之间的连接来实现相邻节点的交换。

注意事项

• 确保处理好边界条件，例如链表为空或只有一个节点的情况。
• 使用虚拟头节点可以避免在交换头部节点时的特殊处理。
• 保持代码的清晰和可读性，特别是指针的移动部分。

这个进阶版本的实现比原始版本稍微复杂一些，但通过合理地使用临时变量和仔细地控制指针移动，可以有效地实现相邻节点的交换。