[数据结构与算法]剑指Offer(第二版)： 46. 把数字翻译成字符串(动态规划) 48. 最长不含重复字符的子字符串 26. 树的子结构 07. 重建二叉树 36. 二叉搜索树与双向链表

/**
解题思路：动态规划
    1、首先考虑转移方程
        if xi + xi-1 不能组成一个数，则dp[i] = dp[i-1]
        if xi + xi-1 能责成一个数，则dp[i] = dp[i-1] + dp[i-2]
    2、考虑边界方程
        首先 dp[1] =1 , 而 dp[2] = 1+1 =2 ,则 反推可以知道 dp[0] = 1;
    
    3、那怎么知道xi和xi-1能不能组成一个数呢，因为ASCII是 0~25,因此01,02,03都不能翻译成a,b,c
       所以xi-1xi 的范围是"10"~"25"

    4、为了方便，我们将数组先转换成字符串
 */
class Solution {
    public int translateNum(int num) {

        String str = String.valueOf(num);

        int len = str.length();

        if(len<2)   return 1;

        int[] dp = new int[len+1];

        dp[0] = dp[1] = 1;

        for(int i=2 ; i<=len ; i++){
            //取前两位
            String subStr = str.substring(i-2,i);

            if(subStr.compareTo("10")>=0 && subStr.compareTo("25")<=0)
                dp[i] = dp[i-2] +dp[i-1];
            else
                dp[i] = dp[i-1]; 
        }
        return dp[len];
    }
}

/**
解题思路:    滑动窗口
    首先是创建一个左右指针，每次移动右指针，不同则直接右移，
    并记录最大值，如果相同，则移动左指针，直到重复字符的下一个
    左指针一直指的是出现重复值得下一个值
 */
class Solution {
    public int lengthOfLongestSubstring(String s) {
        //返回最大值
        int maxDifStr = 0;
        //左右指针
        int lef = 0, rig = 0;

        char[] c_array = s.toCharArray();

        int len = c_array.length;

        //存放值是否重复
        Set<Character> set = new HashSet<>();
        while(rig<len){
            while(set.contains(c_array[rig])){  //注意这里一定是while，直到没有重复值
                set.remove(c_array[lef++]);
            }
            set.add(c_array[rig]);
            maxDifStr = Math.max(maxDifStr ,rig-lef+1);
            rig++;
        }
        return maxDifStr;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null || B == null)
            return false;
        return dfs(A, B) || isSubStructure(A.left , B) || isSubStructure(A.right , B);
    }
    private boolean dfs(TreeNode A , TreeNode B){
        if(B==null) 
            return true;
        if(A == null)
            return false;
        return A.val == B.val && dfs(A.left , B.left) && dfs(A.right , B.right);
    }
}

dsadas

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 /**
 解题思路：
        前序遍历： 中-->左--->右
        中序遍历： 左 --> 中 -->右

        首先我们找根节点：  就是前序遍历的第一个节点

        怎么找到左子树的长度呢：inorder的【0，中节点的坐标-1】  右子树的长度【中节点坐标+1 ， 尾节点】
  */
class Solution {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        int len = preorder.length;

        //边界条件
        if(len == 0)
            return null;
        
        //将中序遍历数组存入到哈希表中
        map = new HashMap<>();
        
        for(int i=0 ; i<len ; i++){
            map.put(inorder[i] , i);
        }

        //开始找其左右节点
        return myBuildTree(preorder,inorder,0,len-1,0,len-1);
    }
    private TreeNode myBuildTree (int[] preorder , int[] inorder , int pre_lef , int pre_rig , int inor_lef, int inor_rig){

        //先写递归条件
        if(pre_lef > pre_rig)
            return null;
        //前序遍历中的根节点下标
        int preorder_root = pre_lef;
        //中序遍历数组中的根节点下标
        int intorder_root = map.get(preorder[preorder_root]);

        //为什么要找中序节点呢？1、因为我们要计算左右子树的长度
        //创建根节点
        TreeNode root = new TreeNode(preorder[preorder_root]);
        //左子树的长度
        int size_leftTree = intorder_root-inor_lef;

        //进行递归

        root.left = myBuildTree(preorder , inorder , preorder_root+1 , preorder_root+size_leftTree , inor_lef, intorder_root-1);
        root.right = myBuildTree(preorder , inorder , preorder_root+size_leftTree+1 , pre_rig , intorder_root+1 , inor_rig);
        
        return root;
    }
}

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
/**
    解题思想：就是正序遍历，只不过改成了链表
 */
class Solution {
    Node head,pre;
    public Node treeToDoublyList(Node root) {
        if(root == null)
            return null;
        dfs(root);
        //首尾相连， head为头节点,pre此时为尾节点
        head.left = pre;
        pre.right = head;
        return  head;
    }
    private void dfs(Node cur){
        if(cur == null)
            return;
        dfs(cur.left);

        if(pre!=null)
            pre.right = cur;
        else 
            head = cur;

        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}