加载中...

递归题集

发表于 2021-03-06| 更新于 2021-03-23|JAVA算法

字数总计:1.5k

70. 爬楼梯

public class arithmetic70 {
    /**
     * 爬楼梯
     * 题目：https://leetcode-cn.com/problems/climbing-stairs/
     * 题解：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/
     */
    @Test
    public void test() {
        System.out.println(climbStairs1(3));
        System.out.println(climbStairs2(3));
        System.out.println(climbStairs3(3));
    }

    public int climbStairs1(int n) {
        int p = 0;
        int q = 0;
        int r = 1;
        for (int i = 1; i <= n; i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

    /**
     * 傻递归超时
     *
     * @param n
     * @return
     */
    public int climbStairs2(int n) {
        if (n <= 3) {
            return n;
        }
        return climbStairs2(n - 1) + climbStairs2(n - 2);
    }

    /**
     * 尾递归
     *
     * @param n
     * @return
     */
    public int climbStairs3(int n) {
        return climbStairs3Course(n, 1, 1);
    }

    public int climbStairs3Course(int n, int a, int b) {
        if (n <= 1) {
            return b;
        }
        // 将上一步的b 传给 a，a + b 传给 b
        return climbStairs3Course(n - 1, b, a + b);
    }
}

方法2的递归太傻中间计算了太多的重复的值，递归千万不能这样用。

方法3中采用了尾递归的形式，相当于把上一步的结果缓存下来，可以重复使用。类似于方法一，这样的递归就很快速。

22. 括号生成

public class arithmetic22 {
    List<String> resultList = new ArrayList<>();

    /**
     * 22. 括号生成
     * 题目：https://leetcode-cn.com/problems/generate-parentheses/
     */
    @Test
    public void test() {
        System.out.println(generateParenthesis1(3));
    }

    public List<String> generateParenthesis1(int n) {
        recursion(n, n, "");
        return resultList;
    }

    /**
     * 递归法
     * @param left   左括号数量
     * @param right  右括号数量
     * @param result 字符串结果
     */
    private void recursion(int left, int right, String result) {
        // 左右括号为0，添加结果
        if (left == 0 && right == 0) {
            resultList.add(result);
        }
        // 左括号剩余可以添加左括号
        if (left > 0) {
            recursion(left - 1, right, result + "(");
        }
        // 这里限制右括号数量大于左括号的时候才能添加右括号，若不大于就添加必定不合法
        if (right > left) {
            recursion(left, right - 1, result + ")");
        }
    }
}

226. 翻转二叉树

public class arithmetic226 {
    /**
     * 226. 翻转二叉树
     * 题目：https://leetcode-cn.com/problems/invert-binary-tree/description/
     */

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode invertTree1(TreeNode root) {
        // 递归终止条件
        if (root == null) {
            return null;
        }
        // 左右子树交换
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = temp;
        // 递归交换当前节点的左子树
        invertTree1(root.left);
        // 递归交换当前节点的右子树
        invertTree1(root.right);
        return root;
    }
}

98. 验证二叉搜索树

利用二叉树中序遍历的特性

public boolean isValidBST(TreeNode root) {
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        double min = -Double.MAX_VALUE;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.val <= min) {
                return false;
            }
            min = root.val;
            root = root.right;
        }
        return true;
    }

94. 二叉树的中序遍历

递归实现

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
         List<Integer> res = new ArrayList<>();
         helper(root, res);
         return res;
    }
    
    public void helper(TreeNode root, List<Integer> res) {
         if (root != null) {
             helper(root.left, res);
             res.add(root.val);
             helper(root.right, res);
         }
     }
}

栈

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        // 手动维护一个栈
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode treeNode = root;
        while (treeNode != null || !stack.isEmpty()) {
            while (treeNode != null) {
                stack.push(treeNode);
                treeNode = treeNode.left;
            }
            treeNode = stack.pop();
            res.add(treeNode.val);
            treeNode = treeNode.right;
        }
        return res;
    }
}

144. 二叉树的前序遍历

递归实现

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    public void helper(TreeNode root, List<Integer> res) {
        if(root != null) {
            res.add(root.val);
            helper(root.left, res);
            helper(root.right, res);
        }
    }
}

栈

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode treeNode = root;
        stack.push(treeNode);
        while (!stack.isEmpty()) {
            treeNode = stack.poll();
            res.add(treeNode.val);
            if (treeNode.right != null) {
                stack.push(treeNode.right);
            }
            if (treeNode.left != null) {
                stack.push(treeNode.left);
            }
        }
        return res;
    }
}

145. 二叉树的后序遍历

1、递归实现

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        // *** 递归方法 ***
        List<Integer> res = new ArrayList();
        helper(res, root);
        return res;
    }

    public void helper(List res, TreeNode root) {
        if (root == null) return;
        helper(res, root.left);
        helper(res, root.right);
        res.add(root.val);
    }
}

2、栈

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        // *** 栈方法实现 ***
        List<Integer> res = new ArrayList();
        if (root == null) return res;
        Deque<TreeNode> stack = new ArrayDeque();
        TreeNode node = root;
        stack.push(node);
        while (!stack.isEmpty()) {
            node = stack.pop();
            res.add(node.val);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        Collections.reverse(res);
        return res;
    }
}

590. N叉树的后序遍历

public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        for (Node cur : root.children) {
            res.addAll(postorder(cur));
        }
        res.add(root.val);
        return res;
    }

589. N叉树的前序遍历

public List<Integer> preorder(Node root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        res.add(root.val);
        if (root.children != null) {
            for (Node child : root.children) {
                res.addAll(preorder(child));
            }
        }
        return res;
    }

429. N叉树的层序遍历

广度优先搜索

public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node node = queue.remove();
                list.add(node.val);
                queue.addAll(root.children);
            }
            result.add(list);
        }
        return result;
    }

优化版本

public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        List<Node> previousLayer = Collections.singletonList(root);
        while (!previousLayer.isEmpty()) {
            ArrayList<Node> currentLayer = new ArrayList<>();
            ArrayList<Integer> previousValues = new ArrayList<>();
            for (Node node : previousLayer) {
                previousValues.add(node.val);
                currentLayer.addAll(node.children);
            }
            result.add(previousValues);
            previousLayer = currentLayer;
        }
        return result;
    }

每次将新的层赋值给旧的层；

104. 二叉树的最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHigh = maxDepth(root.left);
        int rightHigh = maxDepth(root.right);
        return Math.max(leftHigh, rightHigh) + 1;
    }
}

111. 二叉树的最小深度

public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHigh = minDepth(root.left);
        int rightHigh = minDepth(root.right);
        return root.left == null || root.right == null ? leftHigh + rightHigh + 1 : Math.min(leftHigh, rightHigh) + 1;
    }

297. 二叉树的序列化与反序列化(×)

236. 二叉树的最近公共祖先

文章作者: 琦玉

文章链接: https://www.cclblog.cn/2021/03/06/java/arithmetic/5/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自琦玉！

微信
支付宝

相关推荐

HashMap-put方法解析

重载与重写规则

Lambda表达式

本地搜索

由 hexo-generator-search 提供支持