二叉树的最近公共祖先

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        //当 left 和 right 同时为空：说明root的左 / 右子树中都不包含 p,q ，返回 null;
        if( left == null && right == null ){
            return null;
        }
       /*
       当 left 为空 ，right不为空 ：p,q都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：
       1、 p,q 其中一个在 root的 右子树 中，此时 right 指向 pp（假设为 p ）；
       2、 p,q两节点都在 root 的 右子树 中，此时的 right 指向 最近公共祖先节点 ；
       */
        if( left == null ){
            return right;
        }
        //当 left不为空 ， right为空 ：与情况 上面. 同理；
        if(right == null){
            return left;
        }
           //当 left 和 right 同时不为空 ：说明 p, q分列在 root 的 异侧 （分别在 左 / 右子树），因此 root为最近公共祖先，返回 root；
        return root;
    }
}

从前序与中序遍历序列构造二叉树

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
   int len = preorder.length;
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for (int i = 0; i < len; i++) {
            map.put(inorder[i],i);
        }
        return buildTree(preorder,0,len - 1,0,len - 1,map);
    }
    /**
     *
     * @param preorder 前序遍历序列
     * @param preorder_left  前序遍历序列子区间的左边界，可以计算出来
     * @param preorder_right 前序遍历序列子区间右边界，可以计算出来
     * @param inorder_left 中序遍历序列子区间左边界，可以计算出来
     * @param inorder_right 中序遍历序列子区间右边界，可以计算出来
     * @param map 在中序遍历序列里，数值与下标对应关系
     * @return
     */
    private TreeNode buildTree(int[] preorder,  int preorder_left, int preorder_right, int inorder_left, int inorder_right, Map<Integer,Integer> map) {
        if( preorder_left > preorder_right){
            return null;
        }
        //前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        //在中序遍历中定位根节点，在中序的序列中找到对应的根节点的下标位置
        int inorder_root = map.get(preorder[preorder_root]);
        //建立根节点
        TreeNode root = new TreeNode(preorder[preorder_root]);
        //得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        //递归的构造左子树
        root.left = buildTree(preorder,preorder_left + 1,preorder_left + size_left_subtree, inorder_left ,inorder_root - 1,map);
        //递归的构造右子树
        root.right = buildTree(preorder,preorder_left + size_left_subtree + 1,preorder_right,inorder_root+1,inorder_right,map);
        return root;
    }
}

组合

https://leetcode-cn.com/problems/combinations/

全排列

https://leetcode-cn.com/problems/permutations/

全排列II

https://leetcode-cn.com/problems/permutations-ii/