day3

• 两两交换链表中的节点
  
  给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

  • 递归

      public class Solution {
        public ListNode swapPairs(ListNode head) {
            // 如果链表为空或者只有一个节点，无需交换
            if (head == null || head.next == null) {
                return head;
            }
    
            ListNode one = head;
            ListNode two = one.next;
            ListNode three = two.next;
    
            // 交换节点
            two.next = one;
            one.next = swapPairs(three);
    
            return two;
        }
    }
      * 迭代
      ```java
      <p1>很奇妙的一种写法,给每一个节点都抽象化成数字</p1>
      ```java
        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 pre = dummy;
    
              while (pre.next != null && pre.next.next != null) {
                  ListNode one = pre.next;
                  ListNode two = one.next;
                  ListNode three = two.next;
    
                  // 交换节点
                  one.next = three;
                  two.next = one;
                  pre.next = two;
    
                  // 更新 pre 指针
                  pre = one;
              }
    
              return dummy.next;
          }
        }

• 反转二叉树

  • 递归

      class Solution {
       public TreeNode invertTree(TreeNode root) {
    	//递归函数的终止条件，节点为空时返回
    	if(root==null) {
    		return null;
    	}
    	//下面三句是将当前节点的左右子树交换
    	TreeNode tmp = root.right;
    	root.right = root.left;
    	root.left = tmp;
    	//递归交换当前节点的 左子树
    	invertTree(root.left);
    	//递归交换当前节点的 右子树
    	invertTree(root.right);
    	//函数返回时就表示当前这个节点，以及它的左右子树
    	//都已经交换完了
    	return root;
    }