[leetcode]450. Delete Node in a BST二叉搜索树删除节点

二叉树变量只是一个地址

public static void main(String[] args) {

        TreeNode t = new TreeNode(3);

        help(t);

        System.out.println(t.val);

    }

    public static void help(TreeNode t)

    {

        t.val = 6;

    }

上边代码通过地址改变了二叉树，输出为6，但是下边代码却只是传入函数的二叉树变量指向了另一个地址，外界的二叉树变量和二叉树的值没有变，输出还是3

public static void main(String[] args) {

        TreeNode t = new TreeNode(3);

        help(t);

        System.out.println(t.val);

    }

    public static void help(TreeNode t)

    {

        t = new TreeNode6);

    }

所以想改变二叉树，不能改变二叉树变量，而应该通过二叉树变量t调用val,left,right进行赋值，就可以改变，直接改变t只是让t指向另一课树，原本的树没有改变。

下边是答案，思路是先找到节点，再根据节点的不同情况进行操作。

最后的操作很乱，自己都看不下去了，应该递归的改变左右子树，但是眼睛太累了，有空再改吧。

public TreeNode deleteNode(TreeNode root, int key) {

        if(root==null) return null;

        if(root.val==key)

        {

            if (root.left==null)  return root.right;

            if (root.right==null) return root.left;

            TreeNode temp = root.right;

            while (temp.left!=null) temp = temp.left;

            if (root.left.right!=null) temp.left = root.left.right;

            root.left.right = root.right;

            root.val = root.left.val;

            if (root.left.left==null)

            {

                root.right = root.left.right;

                root.left = null;

            }

            else {

                //这里注意，由于两句话都要用到root.left，所以root.left最后再变

                root.right = root.left.right;

                root.left = root.left.left;

            }

        }

        else

        {

            if(root.val>key) root.left = deleteNode(root.left,key);

            else root.right = deleteNode(root.right,key);

        }

        return root;

    }

巴特西

[leetcode]450. Delete Node in a BST二叉搜索树删除节点

最新文章

热门文章