11.21打卡

1. 复制IP （93）

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

class Solution {
    List<String> res = new ArrayList<>();
    char[] cs;
    
    public List<String> restoreIpAddresses(String s) {
        cs = s.toCharArray();
        dfsrestoreIpAddresses(0,cs.length,new ArrayList<>());
        return res;
        
    }
    void dfsrestoreIpAddresses(int idx,int n, List<Integer> cur){
        if(cur.size()>4)
            return;
            //idx 作为当前划分数字的左端点
        if(idx==n){
            if(cur.size()==4){
                //cur 的则是代表子部分的具体划分方案
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < 4; i++) {
                    sb.append(cur.get(i)).append('.');
                }
                res.add(sb.substring(0,sb.length()-1));
            }
        }else {
            for (int i = idx; i <n ; i++) {
                int t =0;
                for (int j = idx; j <=i ; j++) {
                    t=t*10+(cs[j]-'0'); //排成数字
                }
                if(cs[idx]=='0'&&i!=idx) // 025 不合理
                    break;
                if(t>255) break; //超出范围
                cur.add(t);
                dfsrestoreIpAddresses(i+1,n,cur);
                cur.remove(cur.size()-1);
            }
        }
    } 
}

2. 二叉树中序遍历（94）

中序遍历顺序：左-根-右

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stk = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

3. 不同的二叉搜索树（95）

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案

/**
 * 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 List<TreeNode> generateTrees(int n) {
   return dfsgenerateTrees(1,n);
    }

    private List<TreeNode> dfsgenerateTrees(int l, int r) {
        if(l>r) return new ArrayList<>(){{add(null);}};
        List<TreeNode> res = new ArrayList<>();
        for (int i = l; i <=r ; i++) {
            for (TreeNode x : dfsgenerateTrees(l, i - 1)) {
                for (TreeNode y : dfsgenerateTrees(i + 1, r)) {
                    TreeNode root = new TreeNode(i);
                    root.left = x;
                    root.right =y;
                    res.add(root);
                }
            }
        }
        return res;
    }
}