Java日记2018-05-26

晚上下班再补充

7. 重建二叉树
   思路很简单，过程很绕，换句话说结果容易错

public class Solution0526 {
    static HashMap<Integer,Integer> arrl = new HashMap<>();
    public static TreeNode rebulid(int[] pre,int[] ino) {
        for(int i=0;i<ino.length;i++) {
            arrl.put(ino[i], i);
        }
        return rebulidcore(pre,0,pre.length-1,ino,0,ino.length-1);
    }
    public static TreeNode rebulidcore(int[] pre,int pleft,int pright,int[] ino,int ileft,int iright) {
        if(pleft>pright) return null;
        int index = arrl.get(pre[pleft]);
        int treesize = index-ileft;
        TreeNode root = new TreeNode(pre[pleft]);
        //记得给左右树赋值
        root.left = rebulidcore(pre,pleft+1,pleft+treesize,ino,ileft,ileft+treesize-1);
        root.right =rebulidcore(pre,pleft+treesize+1,pright,ino,ileft+treesize+1,iright);
        return root;
    }
    
    public static void main(String[] args) {
        int[] preorder = {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};
        TreeNode root2 = rebulid(preorder,inorder);
        System.out.println(root2.right.left);
    }

}

8. 二叉树的下一个结点
   一直疑惑的是算法给的next节点是个什么鬼

① 如果一个节点的右子树不为空，那么该节点的下一个节点是右子树的最左节点；
② 否则，向上找第一个左链接指向的树包含该节点的祖先节点。

public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
public TreeLinkNode GetNext(TreeLinkNode pNode) {
    if (pNode.right != null) {
        TreeLinkNode node = pNode.right;
        while (node.left != null)
            node = node.left;
        return node;
    } else {
        while (pNode.next != null) {
            TreeLinkNode parent = pNode.next;
            if (parent.left == pNode)
                return parent;
            pNode = pNode.next;
        }
    }
    return null;
}

9. 用两个栈实现队列

Stack<Integer> in = new Stack<Integer>();
Stack<Integer> out = new Stack<Integer>();

public void push(int node) {
    in.push(node);
}

public int pop() throws Exception {
    if (out.isEmpty())
        while (!in.isEmpty())
            out.push(in.pop());

    if (out.isEmpty())
        throw new Exception("queue is empty");

    return out.pop();
}