蓝桥杯定向刷题：递归篇

1、合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

/**
 * 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 mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode root = new ListNode();
        ListNode temp = root;
        while(l1 != null && l2 != null){
            if(l1.val > l2.val){
                temp.next = l2;
                temp = temp.next;
                l2 = l2.next;
            }else{
                temp.next = l1;
                temp = temp.next;
                l1 = l1.next;
            }
        }
        if(l1 == null)
            temp.next = l2;
        else if(l2 == null)
            temp.next = l1;
        return root.next;
    }
}

经验： 水题一遍过，注意while逻辑。

2.二叉树坡度

给定一个二叉树，计算 整个树 的坡度 。 一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。 整个树 的坡度就是其所有节点的坡度之和。

/**
 * 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 {
    int gradroot = 0;
    public int findTilt(TreeNode root) {
        if(root == null)
            return 0;
        caculate(root);
        return gradroot;
    }

    public int caculate(TreeNode root){
        if(root.left == null && root.right == null){
            return root.val;
        }else{
            int left;
            int right;
            if(root.left == null)
                left = 0;
            else
                left = caculate(root.left);
            if(root.right == null)
                right = 0;
            else
                right = caculate(root.right);
            gradroot += Math.abs(right - left);
            return root.val + right + left;
        }
    }
}

经验： 此题一遍过，有一定难度，本来还想着再构造一棵树来记录值的后来发现返回值填和，坡度直接累加即可！

3.二叉搜索树最小节点距离

给定一个二叉搜索树的根节点 root，返回树中任意两节点的差的最小值。

/**
 * 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 {
    LinkedList list = new LinkedList();
    public int minDiffInBST(TreeNode root) {
        getValue(root);
        Collections.sort(list);
        int min = Integer.MAX_VALUE;
        for(int i = 0; i