分类：算法

public static void main(String[] args){
    BinaryTree tree = create();
    MidOrderPrint(tree);
}


static class BinaryTree{
    String data;
    BinaryTree left;
    BinaryTree right;

    public BinaryTree(String data) {
        this.data = data;
    }
}

/**
 * ........... a
 * ........../.....\
 * ........b........c
 * ....../....\
 * ....d........e
 * .....\ ...../
 * ......f....g
 * dfbgeac
 */
private static BinaryTree create(){
    BinaryTree a = new BinaryTree("a");

    BinaryTree b = new BinaryTree("b");
    BinaryTree c = new BinaryTree("c");
    a.left = b;
    a.right = c;

    BinaryTree d = new BinaryTree("d");
    BinaryTree e = new BinaryTree("e");

    b.left = d;
    b.right = e;

    BinaryTree f = new BinaryTree("f");
    BinaryTree g = new BinaryTree("g");

    d.right = f;

    e.left = g;

    return a;
}

static void MidOrderPrint(BinaryTree tree){
    if(tree == null) return ;

    Stack<BinaryTree> stack = new Stack<>();
    BinaryTree cur = tree;

    while(!stack.isEmpty() || cur != null){
        if(cur != null){
            stack.push(cur);
            cur = cur.left;
        }else{
            cur = stack.pop();
            System.out.print(cur.data);
            cur = cur.right;
        }
    }
}

public static void main(String[] args){
    int[][] arrs = new int[][]{
            {1, 3, 4},
            {1, 2, 5},
            {0, 7, 5, 8}
    };

    int[] result = merge(arrs);

    for(int num : result){
        System.out.print(num+" ");
    }
}


private static int getAllCount(int[][] arrs){
    int size = 0;
    for(int[] item : arrs){
        if(item == null) continue;
        size += item.length;
    }
    return size;
}

private static int[] getArrayIdxsAndSet_0(int size){
    int[] idxs = new int[size];
    // 初始化为零
    for(int i = 0; i < idxs.length; i++){
        idxs[i] = 0;
    }
    return idxs;
}

public static int[] merge(int[][] arrs)  {
    if(arrs == null) return null;

    int allCount = getAllCount(arrs);

    int[] result = new int[allCount];
    int[] arrayIdxs = getArrayIdxsAndSet_0(arrs.length);

    for(int resultIdx = 0; resultIdx < allCount; resultIdx++){

        int minValue = 0;
        int minArrayIdx = 0;
        boolean tempNotSet = true;

        for(int i = 0; i < arrs.length; i++){
            int currentIdx = arrayIdxs[i];

            if(currentIdx < arrs[i].length){
                if(tempNotSet){
                    tempNotSet = false;
                    minValue = arrs[i][currentIdx];
                    minArrayIdx = i;
                }else if(minValue > arrs[i][currentIdx]) {
                    minValue = arrs[i][currentIdx];
                    minArrayIdx = i;
                }
            }
        }

        arrayIdxs[minArrayIdx]++;
        result[resultIdx] = minValue;
    }

    return result;
}

实例：
Given nums = [2, 7, 11, 15], target = 9,
 Because nums[0] + nums[1] = 2 + 7 = 9,
 return [0, 1].

public int[] twoSum(int[] nums, int target) {
Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target – nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException(“No two sum solution”);
}