二叉树.md

*.重建二叉树

问题描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解析：这个问题的关键在于知晓前序遍历与中序遍历的关联，比如在中序遍历中找到前序遍历的首节点，则整个二叉树可以被分成左右两部分。通过这种规律我们可以递归的划分数组来构建二叉树。

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    if (pre == null || in == null || pre.length != in.length)return null;
    return run(pre, 0, pre.length - 1, in, 0, in.length - 1);
}
public TreeNode run(int [] pre, int preleft, int preright,int [] in, int inleft, int inright){
    if (inleft > inright || preleft > preright)return null;
    TreeNode root = new TreeNode(pre[preleft]);
    for (int i = inleft; i <= inright; i++){
        if (pre[preleft] == in[i]){//找到当前树（子树）的根节点
            //递归的求解左右子树
            root.left = run(pre, preleft + 1, i - inleft + preleft, in, inleft, i - 1);
            root.right = run(pre, i - inleft + preleft + 1, preright, in, i + 1, inright);
            break;
        }
    }
    return root;
} 

*.树的子结构

问题描述：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

解析：判断A是不是B子结构就需要判断B中是不是有一个子树与A完全相同。策略为递归：判断当前树、判断左子树、判断右子树。

public boolean HasSubtree(TreeNode root1,TreeNode root2){
    if (root2 == null || root1 == null)return false;
    return isSub(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
}
public boolean isSub(TreeNode root1, TreeNode root2){
    if (root2 == null)return true;
    if (root1 == null)return false;
    if (root1.val == root2.val){
        return isSub(root1.left, root2.left) && isSub(root1.right, root2.right);
    }else{
        return false;
    }
}

*.二叉搜索树的后序序列

问题描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。

解析：后序遍历的规律是根节点在最后并能将数组根据大小划分为作为子树。

public boolean VerifySquenceOfBST(int [] sequence) { 
    if (sequence == null || sequence.length == 0)return false;
    return run(sequence, 0, sequence.length - 1);
}
public boolean run(int[] arr, int l, int r){
    if (r-l<= 0)return true;
    int i = l;
    boolean flag = true;
    while (i < r && arr[i] < arr[r]){
        i++;//找到左右子树的划分点
    }
    flag = flag&&run(arr, l, i-1);//递归左子树
    int ll = i;
    while (i < r){
        if (arr[i] < arr[r])return false;//判断右子树在大小上合不合法
        i++;
    }
    return flag&&run(arr, ll, r-1);//递归右子树
}

*.二叉树路径

问题描述：输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

解析：深度遍历的思想，到达该节点判断是否符合要求（值符合+叶节点）。

private ArrayList<ArrayList<Integer>>arr = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
    DFS(root, target);
    return arr;
}
public void DFS(TreeNode root,int target){
    if (root == null)return;
    list.add(root.val);
    int size = list.size();
    if (root.val == target && root.left == null && root.right == null){
        arr.add(new ArrayList<Integer>(list));
    }
    DFS(root.left, target - root.val);
    DFS(root.right, target - root.val);
    list.remove(list.size() - 1);
}

*.平衡二叉树

问题描述：输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

解析：平衡二叉树的关键是左右子树高度差不超过1，函数返回层数来判断高度差。只要有一棵子树不是平衡二叉树整棵树就不是平衡二叉树。

public boolean IsBalanced_Solution(TreeNode root) {
    boolean[] res = new boolean[1];
    res[0] = true;
    getHeight(root, 1, res);
    return res[0];
}
public int  getHeight(TreeNode root, int level, boolean[] res){
    if (root == null)return level;
    int left = getHeight(root.left, level+1, res);
    if (!res[0])return level;
    int right = getHeight(root.right, level+1, res);
    if (!res[0])return level;
    if (Math.abs(left-right) > 1){
        res[0] = false;
    }
    return Math.max(left, right);
}

*.中序遍历的下一个节点

问题描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

解析：若是该节点有右子树，则找右子树的最左，若是没有右子树，就向上寻找，直至满足该节点是其父节点的左孩子，返回父节点。

public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if (pNode == null)return null;
        if (pNode.right != null){
            TreeLinkNode tmp = pNode.right;
            while(tmp.left != null){
                tmp = tmp.left;
            }
            return tmp;
        }
        TreeLinkNode parent = pNode.next;
        while(parent != null && pNode != parent.left){
            pNode = parent;
            parent = pNode.next;
        }
        return parent;
    }

*.序列化与反序列化

问题描述：请实现两个函数，分别用来序列化和反序列化二叉树

解析：若是两棵树完全相同，则其序列化相同

//先序
public String Serialize(TreeNode head) {
    if (head == null) {
        return "#!";
    }
    String res = head.val + "!";
    res += Serialize(head.left);
    res += Serialize(head.right);
    return res;
}
public TreeNode Deserialize(String preStr) {
    String[] values = preStr.split("!");
    Queue<String> queue = new LinkedList<String>();
    for (int i = 0; i != values.length; i++) {
        queue.offer(values[i]);
    }
    return reconPreOrder(queue);
}
public static TreeNode reconPreOrder(Queue<String> queue) {
    String value = queue.poll();
    if (value.equals("#")) {
        return null;
    }
    TreeNode head = new TreeNode(Integer.valueOf(value));
    head.left = reconPreOrder(queue);
    head.right = reconPreOrder(queue);
    return head;
}

95. 不同的二叉搜索树 II

问题描述：给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。

解析：递归思路，给dfs一个集合区间，得到一个树集合。递归终止条件为区间不合法，通过遍历所有可能的根节点，从而获得左右子树的区间，通过dfs构建左右子树的集合，遍历所有左右子树的组合来构建所有树的集合

//先序
public List<TreeNode> generateTrees(int n) {
    if (n == 0)return new ArrayList<>();
    return dfs(1, n);
}
public List<TreeNode> dfs(int start, int end){
    List<TreeNode> res = new ArrayList<>();
    if (start > end){
        res.add(null);
        return res;
    }
    for (int i = start; i <= end; i++){
        List<TreeNode> left = dfs(start, i - 1);
        List<TreeNode> right = dfs(i + 1, end);
        for (TreeNode leftNode : left){
            for (TreeNode rightNode : right){
                TreeNode curNode = new TreeNode(i);
                curNode.left = leftNode;
                curNode.right = rightNode;
                res.add(curNode);
            }
        }
    }
    return res;
}

96. 不同的二叉搜索树

问题描述：给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

解析：
设定：G(n): 长度为n的序列能构成的不同二叉搜索树的个数。
     F(i, n): 以i为根、序列长度为n的不同二叉搜索树个数。
明显有：G(n)=∑F(i,n)
另有：F(i,n)=G(i−1)⋅G(n−i)
可以推导出：G(n)=∑G(i−1)⋅G(n−i)

//先序
public int numTrees(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int len = 2; len <= n; len++){
        for (int i = 1; i <= len; i++){
            dp[len] += dp[i - 1] * dp[len - i];
        }
    }
    return dp[n];
}