深刻理解递归中的“递”与“归”

21 阅读 0 评论 0 点赞

二叉树

二叉树的特性天然就需要使用递归来解决。

104. 二叉树的最大深度

在这里插入图片描述

该问题的边界条件是：空节点。
计算机是怎么执行递归的？
- 当程序执行“递”动作时，计算机使用栈保存这个发出“递”动作的对象，程序不断“递”，计算机不断压栈，直到边界时，程序发生“归”动作，正好将执行的答案“归”给栈顶元素，随后程序不断“归”，计算机不断出栈，直到返回原问题的答案，栈空。

	public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int maxLeft = maxDepth(root.left);
        int maxRight = maxDepth(root.right);
        return Math.max(maxLeft, maxRight) + 1;
    }

100.相同的树

public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null && q!= null) {
            return false;
        }
        if (p != null && q == null) {
            return false;
        }
        if (q.val != p.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

101.对称二叉树

public boolean isSymmetric(TreeNode root) {
        if (root == null)
        return true;
        return isSameTree(root.left, root.right);

    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null && q!= null) {
            return false;
        }
        if (p != null && q == null) {
            return false;
        }
        if (q.val != p.val) {
            return false;
        }
        return isSameTree(p.left, q.right) && isSameTree(p.right, q.left);
    }

110. 平衡二叉树

此问题可以拆解成：当前节点是否平衡 && 节点的左子树是否平衡 && 节点的右子树书否平衡

	public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.abs(getHight(root.left) - getHight(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int getHight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHight(root.left), getHight(root.right)) + 1;
    }

提前返回结果

	public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return getHight(root) != -1;
    }

    private int getHight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHight = getHight(root.left);
        if (leftHight == -1) {
            return -1;
        }
        int rightHight = getHight(root.right);
        if (rightHight == -1 || Math.abs(leftHight - rightHight) > 1) {
            return -1;
        }
        return Math.max(leftHight, rightHight) + 1;
    }

199. 二叉树的右视图

DFS解法

	public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        f(root, 0, ans);
        return ans;
    }

    private void f(TreeNode root, int high, List<Integer> ans) {
        if (root == null) {
            return;
        }
        // 每次记录和树高相同的节点，因为左视图就可以从左子树开始，右视图就从右子树开始就好了
        if (high == ans.size()){
            ans.add(root.val);
        }
        f(root.right, high + 1, ans);
        f(root.left, high + 1, ans);
    }

BFS，使用队列

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if (root == null) {
            return ans;
        }
        queue.add(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == 0) {
                    ans.add(node.val);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
            }
        }
        return ans;
    }

树的遍历

在这里插入图片描述

144.前序遍历

根结点 —> 左子树 —> 右子树

    private void preOrderTraverse(TreeNode root) {
        if (root != null) {
            System.out.print(root.val + " ");
            preOrderTraverse(root.left);
            preOrderTraverse(root.right);
        }
    }

非递归版本

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();
        // 初始化栈
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            // 前序遍历，优先访问根节点。然后访问左子树，最后访问右子树
            ans.add(node.val);
            // 先访问左子树，那右子树可以先入栈后访问
            if (node.right != null) {
                stack.push(node.right);
            }
            // 左子树先访问，因此后入栈先访问
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return ans;
    }

非递归统一写法

    public List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                ans.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                cur = cur.right;
            }
        }
        return ans;
    }

94.中序遍历

左子树 —> 根节点 —> 右子树

    private void inOrderTraverse(TreeNode root) {
        if (root != null) {
            preOrderTraverse(root.left);
            System.out.print(root.val + " ");
            preOrderTraverse(root.right);
        }
    }

非递归统一版本

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                ans.add(cur.val);
                cur = cur.right;
            }
        }
        return ans;
    }

145.后序遍历

左子树 —> 右子树 —> 根节点

    private void postOrderTraverse(TreeNode root) {
        if (root != null) {
            preOrderTraverse(root.left);
            preOrderTraverse(root.right);
            System.out.print(root.val + " ");
        }
    }

栈遍历版本：建议先做中序遍历，后序只是在中序上多了一些操作。

与中序的不同之处在于：

中序遍历中，从栈中弹出的节点，其左子树是访问完了，可以直接访问该节点，然后接下来访问右子树。
后序遍历中，从栈中弹出的节点，我们只能确定其左子树肯定访问完了，但是无法确定右子树是否访问过。
因此，我们在后序遍历中，引入了一个prev来记录历史访问记录。

当访问完一棵子树的时候，我们用prev指向该节点。
这样，在回溯到父节点的时候，我们可以依据prev是指向左子节点，还是右子节点，来判断父节点的访问情况。

	List<Integer> ans = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        //主要思想：
        //由于在某颗子树访问完成以后，接着就要回溯到其父节点去
        //因此可以用prev来记录访问历史，在回溯到父节点时，可以由此来判断，上一个访问的节点是否为右子树
        while (root != null || !stack.isEmpty()) {
            // 左子树全部入栈
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                //从栈中弹出的元素，左子树一定是访问完了的
                root = stack.pop();
                //判断右子树是否是最后一个，或者已经访问过了。
                //满足上面条件就说明可以加入结果集了
                if (root.right == null || prev == root.right) {
                    ans.add(root.val);
                    //更新历史访问记录，这样回溯的时候父节点可以由此判断右子树是否访问完成
                    prev = root;
                    root = null;
                } else {
                    //如果右子树没有被访问，那么将当前节点压栈，知道该节点的最后一个右子树
                    //右子树全部压栈
                    stack.push(root);
                    root = root.right;
                }
            }
        }
        return ans;

102. 层序遍历

    public void levelTraverse(TreeNode root) {
        if (root == null) {
            return;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val+"  ");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

102. 深度遍历

    public void depthOrderTraverse(TreeNode root) {
        if (root == null) {
            return;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val+"  ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

98. 验证搜索二叉树

前序遍历
注意，Java最大值有边界值，不像python有无穷大的概念

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean isValidBST(TreeNode node, long left, long right) {
        if (node == null) {
            return true;
        }
        long x = node.val;
        return left < x && x < right && isValidBST(node.left, left, x) &&isValidBST(node.right, x, right);
    }

中序遍历

class Solution {
    private long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 左子树不是搜索二叉树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 中序遍历先遍历左子树，然后根节点，最后右子树。这里只能判断否，不能判断true
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 右子树是否为搜索二叉树
        return isValidBST(root.right);
    }
}

后序遍历

	public boolean isValidBST(TreeNode root) {
        return dfs(root)[1] != Long.MAX_VALUE;
    }

    private long[] dfs(TreeNode node) {
        if (node == null) {
            return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};
        }
        long[] left = dfs(node.left);
        long[] right = dfs(node.right);
        long x = node.val;
         // 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了
        if (x <= left[1] || x >= right[0]) {
            return new long[]{Long.MIN_VALUE, Long.MAX_VALUE};
        }

        return new long[]{Math.min(left[0], x), Math.max(right[1], x)};
    }

111. 二叉树的最小深度

层次遍历

		public int minDepth(TreeNode root) {
            if (root == null){
                return 0;
            }
            int ans = 0;
            LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
            // 层次遍历只要根节点就可以返回
            queue.add(root);
            while(!queue.isEmpty()) {
                ans++;
                int size  = queue.size();
                while(size > 0){
                    TreeNode node = queue.poll();
                    size--;
                    if (node.left == null && node.right == null){
                        // 遇到根节点了
                        return ans;
                    }
                    if (node.left != null){
                        queue.add(node.left);
                    }
                    if (node.right != null){
                        queue.add(node.right);
                    }
                }
            }
            return ans;
        }

递归
- 那么这样写为什么不对呢

	public int minDepth(TreeNode root) {
        if(root==null) return 0;
        if (root.left == null && root.right == null) {
            return 1;
        }
        int left=minDepth(root.left);
        int right=minDepth(root.right);
        return Math.min(left,right)+1;
    }

叶子节点的定义是对的，但是树的高度没有定义对。
比如：这样的树的高度定义是2，而不是1。
树的高度定义为：

若左子树为空，那么高度就等于右子树高度+1
若右子树为空，那么高度就等有左子树高度+1
若左右子树都为空，那么高度就为1.
自底向上: 树的最大高度这样写也没有问题
定义 minDepth(root) 表示以节点 root 为根的树的最小深度。

分类讨论：

如果 node 是空节点，由于没有节点，返回 0。
如果 node 没有右儿子，那么深度就是左子树的深度加一，即 dfs(node)=dfs(node.left)+1。
如果 node 没有左儿子，那么深度就是右子树的深度加一，即 dfs(node)=dfs(node.right)+1。
如果 node 左右儿子都有，那么分别递归计算左子树的深度，以及右子树的深度，二者取最小值再加一，即

class Solution {
    public int minDepth(TreeNode root) {
        // 空节点就没有高度，返回0
        if(root==null) return 0;
        // 左右子树都为空，则只有根节点，返回高度1
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 若左子树为空
        if (root.left == null) {
            return minDepth(root.right) + 1;
        }
        // 若右子树为空
        if (root.right == null) {
            return minDepth(root.left) + 1;
        }
        // 若左右子树都不为空，返回左右子树高度的最小值 在+1。 （＋1是因为当前节点，返回+1后就是当前节点的高度了）。子树的高度+1 = 当前高度
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

112. 路径之和

public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        targetSum -= root.val;
        // root是叶子节点
        if (root.left == root.right) {
            return targetSum == 0;
        }
        return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
    }

129. 求根节点的到叶子节点数字之和

当你的题目做多了，就知道这类题目该怎么做了

class Solution {
    private int sum = 0;
    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return sum;
    }
    public void dfs(TreeNode node, int currVal) {
        if (node == null) {
            return;
        }
        currVal = currVal * 10 + node.val;
        if (node.left == node.right) {
            sum += currVal;
            return;
        }
        dfs(node.left, currVal);
        dfs(node.right, currVal);
    }
}

1448. 统计二叉树中好节点的数目

class Solution {
    private int ans = 0;
    public int goodNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root, root.val);
        return ans;
    }
    private void dfs(TreeNode node, int max) {
        if (node == null) {
            return;
        }
        int x = max;
        if (node.val >= max) {
            ans ++;
            x = node.val;
        }
        dfs(node.left, x);
        dfs(node.right, x);
    }
}

987. 二叉树的垂序遍历

class Solution {
    private Map<Integer, List<Integer>> map = new HashMap<>();
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<int[]>> groups = new TreeMap<>();
        dfs(root, 0, 0, groups);
        List<List<Integer>> ans = new ArrayList<>(groups.size());
        // 当前col Key下的元素排序，value: List<int[]> 是一个List
        for (List<int[]> g: groups.values()) {
            // 先高排序，在层次上面的优先加入，对于层次一样的，按照值排序
            g.sort((a,b) -> a[0] != b[0] ? a[0]- b[0] : a[1] - b[1]);
            List<Integer> vals = new ArrayList<>(g.size());
            for (int[] p : g) {
                vals.add(p[1]);
            }
            ans.add(vals);
        }
        return ans;

    }

    private void dfs(TreeNode node, int row, int col, Map<Integer, List<int[]>> groups) {
        if (node == null) {
            return;
        }
        groups.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, node.val});
        dfs(node.left, row + 1, col -1, groups);
        dfs(node.right, row + 1, col + 1, groups);
    }
}

直接使用三元组

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<int[]> data = new ArrayList<>();
        dfs(root, 0, 0, data);

        List<List<Integer>> ans = new ArrayList<>();
        data.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);
        int lastCol = Integer.MIN_VALUE;
        for (int[] d : data) {
        	// 为什么这样写： 统一垂序的位置放在一起
            if (d[0] != lastCol) {
                lastCol = d[0];
                ans.add(new ArrayList<>());
            }
            ans.get(ans.size() - 1).add(d[2]);
        }
        return ans;
    }

    private void dfs(TreeNode node, int row, int col, List<int[]> data) {
        if (node == null) {
            return;
        }
        data.add(new int[]{col, row, node.val});
        dfs(node.left, row + 1, col - 1, data);
        dfs(node.right, row + 1, col + 1, data);
    }
}

226. 翻转二叉树

 	public TreeNode invertTree(TreeNode root) {
		if (root == null) {
            return null;
        }
        // 需要记录当前节点的左右子树
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = invertTree(right);
        root.right = invertTree(left);
        return root;
    }

617. 合并二叉树

 public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 为空，返回另一个二叉树
		if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }

1026. 节点与其祖先的最大差值

class Solution {
	private int ans = 0;
    public int maxAncestorDiff(TreeNode root) {
		if (root == null) {
			return 0;
		}
		dfs(root, root.val, root.val);
        return ans;
    }
	private void dfs(TreeNode node, int min, int max) {
		if (node == null) {
            return;
        }
		if (node.val > max) {
            ans = Math.max(ans, node.val - min);
            max = node.val;
        }
        if (node.val < min) {
            ans = Math.max(ans, max - node.val);
            min = node.val;
        }
        dfs(node.left, min, max);
        dfs(node.right, min, max);
	}
}

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

在这里插入图片描述

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
         //当前节点是null 或者 当前节点是p 或者当前节点是q
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //在当前节点左右子树都能找到，返回当前节点
        if (left != null && right != null) {
            return root;
        }
        // 只有左子树找到
        if (left != null) {
            return left;
        }
        // 只有右子树找到，或者都找不到。
        return right;
    }
}

[235. 二叉搜索树的最近公共祖先]

在这里插入图片描述

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        int x = root.val;
        if (p.val < x && q.val < x){
            return lowestCommonAncestor(root.left, p,q);
        }
        if(p.val > x && q.val > x) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}

103. 二叉树的锯齿形层次遍历

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean even  = false;
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while(size > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                size--;
            }
            if (even) {
                Collections.reverse(list);
            }
            even = !even;
            ans.add(list);
        }
        return ans;
    }
}

513. 找树左下角的值

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int x = root.val;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            x = node.val;
            if (node.right != null) {
                queue.add(node.right);
            }
            if (node.left != null) {
                queue.add(node.left);
            }
        }
        return x;
    }
}

107. 二叉树的层次遍历II

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while(size > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                size--;
            }
            ans.add(list);
        }
        Collections.reverse(ans);
        return ans;
    }
}

116. 填充每个节点的下一个右侧节点指针同117. 填充每个节点的下一个右侧节点指针II

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node node = null;
            while (size > 0) {
                node = queue.poll();
                node.next = queue.peek();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                size --; 
            }
            node.next = null;
        }
        return root;
    }
}

回溯

17. 电话号码的字母组合

class Solution {
	private String[] MAPPING = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
	private List<String> ans = new ArrayList<String>();

	private char[] digitsCharArray;

	private char[] path;
	public List<String> letterCombinations(String digits) {
		int n  = digits.length();
		if (n == 0) {
			return List.of();
		}
		this.digitsCharArray = digits.toCharArray();
		this.path = new char[n];
		dfs(0);
		return ans;
	}

	private void dfs(int index) {
		if (index == digitsCharArray.length) {
			ans.add(new String(path));
			return;
		}
		for (char c : MAPPING[digitsCharArray[index] - '0'].toCharArray()) {
            path[index] = c;
            dfs(index + 1);
        }

	}

}

子集型回溯

每个元素都可以选或者不选
回溯三问
- 当前操作？枚举第i个数选/不选
- 子问题？从下标≥i的数字中构造子集
- 下一个子问题？从下标≥i + 1的数字中构造子集

78. 子集

站在输入的角度思考
- 每个数可以在子集中（选）
- 也可以不在子集中（不选）
- 叶子是答案

class Solution {
	private List<List<Integer>> ans = new ArrayList<>();
	private ArrayList<Integer> path = new ArrayList<>();
	private int[] nums;
    public List<List<Integer>> subsets(int[] nums) {
		this.nums = nums;
		dfs(0);
		return ans;
    }


	private void dfs(int index) {
		System.out.println("index:" + index + "  path: " + this.path);
		if (index == this.nums.length){
			System.out.println("添加进ans: " + String.valueOf(this.path));
			ans.add(new ArrayList<>(this.path));
			return;
        }
        path.add(this.nums[index]);
		System.out.println("添加进path: " + String.valueOf(this.path));
        dfs(index + 1);
		System.out.println("移除path中: " + String.valueOf(this.path.get(this.path.size() - 1)));
		path.remove(this.path.size() - 1);
		System.out.println("移除后path: " + String.valueOf(this.path));
		dfs(index + 1);
    }
}

输出：结构式一棵树，加入或者不加入

		index:0  path: []
		添加进path: [1]
		index:1  path: [1]
		添加进path: [1, 2]
		index:2  path: [1, 2]
		添加进path: [1, 2, 3]
		index:3  path: [1, 2, 3]
		添加进ans: [1, 2, 3]
		移除path中: 3
		移除后path: [1, 2]
		index:3  path: [1, 2]
		添加进ans: [1, 2]
		移除path中: 2
		移除后path: [1]
		index:2  path: [1]
		添加进path: [1, 3]
		index:3  path: [1, 3]
		添加进ans: [1, 3]
		移除path中: 3
		移除后path: [1]
		index:3  path: [1]
		添加进ans: [1]
		移除path中: 1
		移除后path: []
		index:1  path: []
		添加进path: [2]
		index:2  path: [2]
		添加进path: [2, 3]
		index:3  path: [2, 3]
		添加进ans: [2, 3]
		移除path中: 3
		移除后path: [2]
		index:3  path: [2]
		添加进ans: [2]
		移除path中: 2
		移除后path: []
		index:2  path: []
		添加进path: [3]
		index:3  path: [3]
		添加进ans: [3]
		移除path中: 3
		移除后path: []
		index:3  path: []
		添加进ans: []

站在答案的角度思考
- 枚举第一个数选谁
- 枚举第二个数选谁。。。。。
- 每个节点都是答案

注意：

[1,2] 和[2, 1] 是重复的子集
为了避免重复
下一个数应该大于当前选择的数
回溯三问：
- 当前操作？枚举一个下标j ≥ i的数字，加入path
- 子问题？从下标≥ i的数字中构造子集
- 下一个子问题？从下标 ≥ j + 1 的数字中构造子集

class Solution {
	private List<List<Integer>> ans = new ArrayList<>();
	private ArrayList<Integer> path = new ArrayList<>();
	private int[] nums;
    public List<List<Integer>> subsets(int[] nums) {
		this.nums = nums;
		dfs2(0);
		return ans;
    }

	private void dfs2(int index) {
		System.out.println("index:" + index + "  path: " + this.path);
		// 递归到每一个节点都可能是答案
		ans.add(new ArrayList<>(this.path));
		System.out.println("添加进ans: " + String.valueOf(this.path));
		if (index == this.nums.length){
			return;
		}
		System.out.println("========================index:" + index);
		// 枚举每一种可能性
		for (int j = index; j < this.nums.length; j++) {
			System.out.println("j:" + j);
            this.path.add(this.nums[j]);
            System.out.println("添加进path: " + String.valueOf(this.path));
            dfs2(j + 1);
            System.out.println("移除path中: " + String.valueOf(this.path.get(this.path.size() - 1)));
            path.remove(this.path.size() - 1);
            System.out.println("移除后path: " + String.valueOf(this.path));
        }
		System.out.println("========================index" + index + "结束");
	}
}

输出

		index:0  path: []
		添加进ans: []
		========================index:0
		j:0
		添加进path: [1]
		index:1  path: [1]
		添加进ans: [1]
		========================index:1
		j:1
		添加进path: [1, 2]
		index:2  path: [1, 2]
		添加进ans: [1, 2]
		========================index:2
		j:2
		添加进path: [1, 2, 3]
		index:3  path: [1, 2, 3]
		添加进ans: [1, 2, 3]
		移除path中: 3
		移除后path: [1, 2]
		========================index2结束
		移除path中: 2
		移除后path: [1]
		j:2
		添加进path: [1, 3]
		index:3  path: [1, 3]
		添加进ans: [1, 3]
		移除path中: 3
		移除后path: [1]
		========================index1结束
		移除path中: 1
		移除后path: []
		j:1
		添加进path: [2]
		index:2  path: [2]
		添加进ans: [2]
		========================index:2
		j:2
		添加进path: [2, 3]
		index:3  path: [2, 3]
		添加进ans: [2, 3]
		移除path中: 3
		移除后path: [2]
		========================index2结束
		移除path中: 2
		移除后path: []
		j:2
		添加进path: [3]
		index:3  path: [3]
		添加进ans: [3]
		移除path中: 3
		移除后path: []
		========================index0结束

DP

贪心

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处：免费源码网-免费的源码资源网站 » 深刻理解递归中的“递”与“归”

点赞(0) 打赏

本文分类：文章资讯
本文标签：深刻理解递归中的“递”与“归”
浏览次数：21 次浏览
本文链接：https://freeymw.com/article/27248.html

评论列表共有 0 条评论

暂无评论

深刻理解递归中的“递”与“归”

二叉树

树的遍历

[235. 二叉搜索树的最近公共祖先]

116. 填充每个节点的下一个右侧节点指针 同117. 填充每个节点的下一个右侧节点指针II

回溯

子集型回溯

DP

贪心

评论列表 共有 0 条评论

发表评论 取消回复

116. 填充每个节点的下一个右侧节点指针同117. 填充每个节点的下一个右侧节点指针II

评论列表共有 0 条评论

发表评论取消回复