leetcode99题Rocover Binary search tree

老师您好leetcode这道题我看了您的第一个solution

但是我不太明白原理是什么还有为什么题目要改变一个树但是code里面就改变一下 list的位置就好了做这种题的解题思路应该是怎样的谢谢

源自：二分搜索树 1-1 为什么要研究树结构

收起

1回答

liuyubobobo 2021-08-07 06:43:30

“为什么题目要改变一个树但是code里面就改变一下 list的位置就好了？”

list 中存的是树中每一个节点的引用，改变引用，原来树中的相应节点就会发生改变。他们指向的是同一个内存地址。

这个代码的整体思路是：

1）首先中序遍历整个树。如果整个树是正确的 BST，中序遍历的结果应该是有序的。

2）但现在有两个节点的元素是错误的，在这两个节点的位置，一定是反序的，即：list.get(i - 1).val > list.get(i).val

3）找到这两个节点（a 和 b），交换着两个节点的 val 即可。

继续加油！：）

提问者 weixin_慕圣6334738 #1

老师我想补充个小问题在您的解法中您先用inorder来存节点的引用那么是不是list中存的每个节点其实都还包含了该节点下面所有的子节点只是当我取list.get(i -1)的时候他默认取了最顶部的root的值

2021-09-16 14:09:42
提问者 weixin_慕圣6334738 #2

还有一个关于java的点我不太明白，就是一般情况下，我往一个method的参数里面传入一个int值，然后在method里面改变这个值，但是在method外这个值还是不会变的，但是为什么在这里用treenode的时候，就可以通过引用进行改变呢～

2021-09-16 14:20:32
liuyubobobo 回复提问者 weixin_慕圣6334738 #3

1）“是不是list中存的每个节点其实都还包含了该节点下面所有的子节点” list 中只是存储了这个节点 TreeNode，但是，你可以通过 TreeNode.left 和 TreeNode.right 访问这个节点的左右子节点。

2）“当我取list.get(i -1)的时候他默认取了最顶部的root的值” 取出的就是 list 中存放的第 i-1 个节点，不是 root。

3）因为 int 是基本数据类型，不是类对象。在 Java 中，基本数据类型的参数都是传值，类对象的参数都是传引。这个概念非常非常重要，一定要搞清楚。使用任何编程语言，写任何程序，都有这个问题。

2021-09-16 23:57:02