波波老师问一个二叉树中removeElement问题

Question

在被移除的元素和当前node的val相等时,我出现了栈溢出的bug
//Node succssor = new Node(findMin(node.right).val);->被注释了
1 Node successor= findMin(node.right);
2 successor.right = removeMin(node.right);
3 successor.left = node.left;
4 node.left = node.right = null;
5 return successor;
此时运行是无异常的,当2和3调换之后,就出现了栈溢出的情况,我debug发现是successor自己指向了自己,我发现本质问题是java在实例化对象的时候,一个node.right存储节点指向引用变量,我现在是让这个node.right指向了新的successor引用变量,之前的引用变量会被覆盖嘛?

Answer 1

liuyubobobo 2020-04-17 08:21:52

removeMin(node.right) 中的逻辑是沿着node.right的左孩子一直向左找，直到无法继续向左。

successor 本身就是 node.right 最左的孩子，如果你先让 successor.left = node.left，相当于构成了一个环。画一个图试试看？这就将使得 removeMin 陷入无穷递归。

另外，提问请将问题放到相关的小节。谢谢。

继续加油！：）

• 提问者 那红尘 #1

  谢谢波波老师的解答!老师的算法讲解真的很棒!期待老师出新的视频!

Answer 2

提问者 那红尘 2020-04-16 21:12:14

还有代码段1换成注释的那段代码,这样即使代码段2和3互换位置也不会出现栈溢出的情况