public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

TreeNode head;
    private void init() {
        //添加一個(gè)頭節(jié)點(diǎn)
        head = new TreeNode(-1);
    }

/**
     * 插入新節(jié)點(diǎn)，假設(shè)新節(jié)點(diǎn)均大于0
     * @param val 插入節(jié)點(diǎn)值
     * @return 插入的節(jié)點(diǎn)
     */
    public TreeNode insert(int val) {
        TreeNode temp = head;
        while (true) {
            if (temp.val < val) {
                //val應(yīng)該在右子樹上
                if (null != temp.right) {
                    temp = temp.right;
                    continue;
                } else {
                    temp.right = new TreeNode(val);
                    return temp.right;
                }
            }
            //應(yīng)該在左子樹上
            if (null != temp.left) {
                temp = temp.left;
                continue;
            }
            temp.left = new TreeNode(val);
            return temp.left;
        }
    }

/**
     * 搜索節(jié)點(diǎn)值
     * @param val
     * @return
     */
    public Pair<TreeNode, TreeNode> find(int val) {
        TreeNode temp = head.right;
        TreeNode parent = head;
        while (null != temp) {
            if (temp.val == val) {
                return Pair.of(temp, parent);
            }
            parent = temp;
            if (temp.val < val) {
                //在右子樹上
                temp = temp.right;
                continue;
            }
            temp = temp.left;
        }
        return null;
    }

/**
     * 1.如果刪除的是葉子節(jié)點(diǎn)直接刪除，
     * 2.如果刪除的節(jié)點(diǎn)只有左子樹或者右子樹，則直接將左子樹或者右子樹節(jié)點(diǎn)放在刪除節(jié)點(diǎn)位置
     * 3.如果刪除節(jié)點(diǎn)同時(shí)右左子樹和右子樹，則將右子樹節(jié)點(diǎn)放在原來節(jié)點(diǎn)位置，將左子樹放在右子樹最左邊節(jié)點(diǎn)左子樹上
     * @param val
     */
    public void delete(int val) {
        //找到刪除節(jié)點(diǎn)，刪除節(jié)點(diǎn)父節(jié)點(diǎn)
        Pair<TreeNode, TreeNode> curAndParent = this.find(val);
        TreeNode cur = curAndParent.getLeft();
        TreeNode parent = curAndParent.getRight();
        //記錄刪除當(dāng)前節(jié)點(diǎn)后，當(dāng)前節(jié)點(diǎn)位置放置哪個(gè)節(jié)點(diǎn)
        TreeNode changed;
        if (null == cur.left && null == cur.right) {
            changed = null;
        } else if (null != cur.left && null != cur.right) {
            TreeNode tempRight = cur.right;
            while (null != tempRight.left) {
                //找到最左側(cè)節(jié)點(diǎn)
                tempRight = tempRight.left;
            }
            tempRight.left = cur.left;
            changed = cur.right;
        } else if (null != cur.left) {
            changed = cur.left;
        } else {
            changed = cur.right;
        }
        if (parent.left == cur) {
            parent.left = changed;
            return;
        }
        parent.right = changed;
    }