一只小码农

每天进步一点点

初识递归

发表于 更新于 分类于 Valine：
本文字数： 6.2k 阅读时长 ≈ 6 分钟
对leetcode上递归easy篇的总结

二叉搜索树的范围和

DFS深度优先搜索

1.递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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 ans;
    public int rangeSumBST(TreeNode root, int low, int high) {
       ans = 0 ;
        dfs(root,low,high);
        return ans;
    }
    public void dfs(TreeNode node,int L,int R){
        if(node!=null){
            if(L<=node.val&&node.val<=R){
                ans+=node.val;
            }
            if(node.val>L){
                dfs(node.left,L,R);
            }
            if(node.val<R){
                dfs(node.right,L,R);
            }
        }
    }
}

2.迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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 int rangeSumBST(TreeNode root, int low, int high) {
        int ans = 0;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node!=null){
                if(node.val>=low&&node.val<=high){
                    ans+=node.val;             //注意：在这里不要写成ans+=node;
                }
                if(node.val>low){
                    stack.push(node.left);
                }
                if(node.val<high){
                    stack.push(node.right);
                }
            }
        }
        return ans;
    }
}

二叉树的最大深度

DFS

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }else{
            int maxLeftHight = maxDepth(root.left);
            int maxRightHighgt = maxDepth(root.right);
            return Math.max(maxLeftHight,maxRightHighgt)+1;
        }
    }
}

面试题：汉诺塔

1
2
3
4
5
6
7
8
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        /**
        将A柱子上面的盘子，通过辅助柱子B移动到C柱子的上面，需要用到递归和分治的算法
        先把上面 n - 1 个盘子从 A 移到 B（子问题，递归）；
		再将最大的盘子从 A 移到 C；
		再将 B 上 n - 1 个盘子从 B 移到 C（子问题，递归）
        **/
        int n = A.size();  //先用n来表示柱子A上盘子的规模
        moveable(n,A,B,C);

    }
    public void moveable(int num,List<Integer>A,List<Integer> B,List<Integer> C){
        if(num == 1){
            C.add(A.remove(A.size()-1));    //只有一个盘子，直接移动即可
            return;
        }else{
            moveable(num-1,A,C,B);         //以C柱为辅助，将A柱上的n-1个圆盘移动至B柱
            C.add(A.remove(A.size()-1));   //将A柱的最大圆盘放在C柱底端
            moveable(num-1,B,A,C);         //以A柱为辅助柱，将B柱的n-1个圆盘移动至C柱
        }
    }
}

递归顺序查找树

给你一个树，请你 按中序遍历 重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。

示例 ：

输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

方法一：中序遍历+构造新的树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * 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 increasingBST(TreeNode root) {
        List<Integer> vals = new ArrayList<Integer>();
        //获取到了升序的数组vals
        inorder(root,vals);
        //下面的过程是重构树的过程，要求没有左节点，只有右节点
        TreeNode ans = new TreeNode(0);
        TreeNode cur = ans;
        for(int v : vals){
            cur.right = new TreeNode(v);
            cur = cur.right;
        }
        return ans.right;   //返回的即为第一个节点，这里也体现出了设立ans的作用，类似于链表中的哨兵，在构建完成之后方便返回
    }

    //中序遍历-----递归部分
    public void inorder(TreeNode node, List<Integer> vals){
        //不要忘了node为空的终止条件
        if(node==null)
            return ;
        inorder(node.left,vals);        //从当前结点出发，先遍历左子树
        vals.add(node.val);                 //node的左子树遍历完成，将node加入数组
        inorder(node.right,vals);       //遍历当前节点的右子树，将其值加入数组
    }
}

方法二：中序递归遍历+更改树的连接关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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 {
    TreeNode cur;    //作为成员变量，可以被各个方法引用
    public TreeNode increasingBST(TreeNode root) {
        TreeNode ans = new TreeNode(0);
        cur = ans;
        inorder(root);
        return ans.right;
    }

    public void inorder(TreeNode node){
        if(node==null)
            return;
        inorder(node.left);
        node.left = null;
        cur.right = node;
        cur = node;
        inorder(node.right);
    }
}

面试题：biNode

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode head = new TreeNode(-1);
    TreeNode prev = head;
    public TreeNode convertBiNode(TreeNode root) {
        makelist(root);
        return head.right;
    }

    public void makelist(TreeNode node){
        //采用中序遍历，最后会得到一个升序的单链表
        //最后返回的仍然是树，但是左子树为空，并且题目要求在原址修改，所以直接返回树即可
        if(node==null){
            return ;
        }
        makelist(node.left);
        prev.right = node;
        prev = node;  
        node.left = null;
        makelist(node.right);
    }
}

​

这个图可以解释上面递归顺序查找树和biNode两道题中类似下面这样的代码

1
2
3
4
5
 cur.right = node;
 cur = node;

prev.right = node;
 prev = node;

第一条指令用于更新结点指向，后一天指令用于prev的指向，即指向下一个元素，方便下一次访问

面试题16.11 跳水板

你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。

返回的长度需要从小到大排列。

二叉树的坡度

给定一个二叉树，计算 整个树 的坡度 。

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

整个树的坡度就是其所有节点的坡度之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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 {
    //成员变量可以不赋初值，局部变量必须要赋初值，
    private int count;
    public int findTilt(TreeNode root) {
        calculate(root);
        return count;
    }
    public int calculate(TreeNode node){
        if(node==null){
            return 0;
        }
        //后期需要用到，所以每次递归的结果用left和right接收一下
        int left = calculate(node.left);
        int right = calculate(node.right);
        count+=Math.abs(left-right);
        return left+right+node.val;    //返回当前结点之和，便于下次递归使用
    }
}
谢谢你的支持哦，继续加油.