【算法系列篇】递归、搜索和回溯（二）

文章目录

• 前言
• 1. 两两交换链表中的节点
• • 1.1 题目要求
  • 1.2 做题思路
  • 1.3 代码实现
  • 2. Pow(X,N)
  • • 2.1 题目要求
    • 2.2 做题思路
    • 2.3 代码实现
    • 3. 计算布尔二叉树的值
    • • 3.1 题目要求
      • 3.2 做题思路
      • 3.3 代码实现
      • 4. 求根节点到叶结点数字之和
      • • 4.1 题目要求
        • 4.2 做题思路
        • 4.3 代码实现

          前言

          前面为大家介绍了关于递归的知识，以及使用递归解决了几个问题，那么这篇文章将带大家巩固一下关于递归的知识。

          1. 两两交换链表中的节点

          https://leetcode.cn/problems/swap-nodes-in-pairs/description/

          1.1 题目要求

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

          示例 1：

          

          输入：head = [1,2,3,4]
          输出：[2,1,4,3]
          

          示例 2：

          输入：head = []
          输出：[]
          

          示例 3：

          输入：head = [1]
          输出：[1]
          

          提示：

          链表中节点的数目在范围 [0, 100] 内
          0 
              public ListNode swapPairs(ListNode head) {
              }
          }
          
              public ListNode swapPairs(ListNode head) {
                  if (head == null || head.next == null) return head;
                  ListNode l1 = swapPairs(head.next.next);
                  ListNode ret = head.next;
                  head.next.next = head;
                  head.next = l1;
                  return ret;
              }
          }
          
              public ListNode swapPairs(ListNode head) {
                  if (head == null || head.next == null) return head;
                  ListNode curNext = head.next.next;
                  ListNode ret = head.next;
                  head.next.next = head;
                  head.next = swapPairs(curNext);
                  return ret;
              }
          }
          
              public double myPow(double x, int n) {
              }
          }
          
              public double myPow(double x, int n) {
              	//处理幂数的正负问题
                  if (n 9->1 代表数字 491
          从根到叶子节点路径 4->0 代表数字 40
          因此，数字总和 = 495 + 491 + 40 = 1026
          

          提示：

          树中节点的数目在范围 [1, 1000] 内
          0 
              public int sumNumbers(TreeNode root) {
              }
          }
          
              public int sumNumbers(TreeNode root) {
                  return dfs(root, 0);
              }
          	//n用来记录当前路径上该节点之前的各个节点的和
              private int dfs(TreeNode root, int n) {
                  if (root == null) return 0;
                  //遇到一个节点就将当前节点的值加在n上
                  n = n * 10 + root.val;
                  //遇到叶子节点就说明当前节点的值计算完成，就返回路径上所以数字和
                  if (root.left == null && root.right == null) return n;
          		//分别计算根节点左右子树上根节点到叶子节点路径上数字和
                  int l = dfs(root.left, n);
                  int r = dfs(root.right, n);
          		//返回左子树和右子树所有路径上数字和
                  return l + r;
              }
          }