Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Example 1:
Input:
1
/
0 2
L = 1
R = 2
Output:
1
\
2
通過這道題我明白了「形參，實(shí)參」這個(gè)概念颊郎。
1.形參變量只有在被調(diào)用時(shí)才分配內(nèi)存單元萧求，在調(diào)用結(jié)束時(shí)历帚， 即刻釋放所分配的內(nèi)存單元。因此甸昏，形參只有在函數(shù)內(nèi)部有效谋右。 函數(shù)調(diào)用結(jié)束返回主調(diào)函數(shù)后則不能再使用該形參變量。
一開始我的代碼：
if (root == null) return null;
if (root.val < L) {
root = root.right;
return trimBST(root, L, R);
}
if (root.val > R) {
root = root.left;
return trimBST(root, L, R);
}
if (root.left != null && root.left.val < L) {
root.left = root.left.right;
}
if (root.right != null && root.right.val > R) {
root.right = root.right.left;
}
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
注意
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
起初我想不通為什么要給root.left和root.right賦值炫彩，明明我已經(jīng)在遞歸中改變了它的孩子的內(nèi)存了啊（root = root.right）絮短。但是由于進(jìn)入了一個(gè)新的函數(shù)江兢，這樣做其實(shí)并沒有改變它孩子的內(nèi)存，而是制造了一個(gè)新的引用（棧內(nèi)存）指向了root.right丁频；而如果這時(shí)我改變r(jià)oot.right的值杉允，root.right會(huì)指向另一塊內(nèi)存，始終不會(huì)對(duì)root造成影響限府。
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) return null;
if (root.val < L) {
return trimBST(root.right, L, R);
}
if (root.val > R) {
return trimBST(root.left, L, R);
}
if (root.left != null && root.left.val < L) {
root.left = root.left.right;
}
if (root.right != null && root.right.val > R) {
root.right = root.right.left;
}
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
Or:
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) return null;
if (root.val < L) return trimBST(root.right, L, R);
if (root.val > R) return trimBST(root.left, L, R);
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
Dec 7 2017 review
今天又蒙逼了夺颤，不知怎么又繞內(nèi)存/引用的問題上了痢缎，我寫了一段測試代碼胁勺，發(fā)現(xiàn)在函數(shù)里改變一個(gè)對(duì)象，那個(gè)對(duì)象竟然真的被改變了独旷。比如我初始化一個(gè)數(shù)組是{1,2,3}（數(shù)組是對(duì)象署穗，它是new出來的），在函數(shù)里改變數(shù)組第三個(gè)元素的值嵌洼，我預(yù)想的是案疲，因?yàn)楹瘮?shù)和它的參數(shù)是保存在方法區(qū)的，函數(shù)參數(shù)中的數(shù)組麻养，其實(shí)只是一個(gè)指向原來arr的引用褐啡，所以我在函數(shù)中改變arr又沒有return回去，按理說是數(shù)組還會(huì)是{1,2,3}吧鳖昌，但事實(shí)并非如此备畦，函數(shù)執(zhí)行完后arr被改變了。我的世界觀又一次崩塌了许昨。懂盐。。
然后我看了下這個(gè)blog
里的例子糕档，看到String拼接那部分才發(fā)現(xiàn)原因莉恼。其實(shí)這個(gè)我早就知道，只是長期不刷算法忘記了。俐银。我傳入的int數(shù)組尿背，參數(shù)里的arr確實(shí)只是一個(gè)引用沒錯(cuò)，但是我改變的不是這個(gè)對(duì)象的引用悉患，我改變的是它里面的元素残家。
我在上面說過，「而如果這時(shí)我改變r(jià)oot.right的值售躁，root.right會(huì)指向另一塊內(nèi)存坞淮，始終不會(huì)對(duì)root造成影響。」為什么會(huì)指向另一塊內(nèi)存陪捷，而不是直接在原來的堆內(nèi)存上修改回窘？用形參實(shí)參來解釋其實(shí)不太嚴(yán)謹(jǐn)，下面是我看的另外一個(gè)問題得出的思考：
靜態(tài)方法會(huì)導(dǎo)致內(nèi)存泄露嗎市袖？
這種寫法不會(huì)造成內(nèi)存泄漏啡直。為什么不會(huì)呢？要想造成內(nèi)存泄漏苍碟，你的工具類對(duì)象本身要持有指向傳入對(duì)象的引用才行酒觅！但是當(dāng)你的業(yè)務(wù)方法調(diào)用工具類的靜態(tài)方法時(shí)，會(huì)生產(chǎn)一個(gè)稱為棧幀(stack frame)的東西（每次方法調(diào)用微峰，JVM都會(huì)生成一個(gè)棧幀）舷丹，當(dāng)方法調(diào)用結(jié)束返回的時(shí)候，當(dāng)前方法棧幀就已經(jīng)被彈出了并且被釋放掉了蜓肆。 整個(gè)過程結(jié)束時(shí)颜凯，工具類對(duì)象本身并不會(huì)持有傳入對(duì)象的引用。
也就是說之前理解的并不對(duì)仗扬，傳入的參數(shù)并不是對(duì)象的引用症概，而是一個(gè)棧幀(stack frame)，或者說棧幀的一部分早芭，我猜是放在stack frame的局部變量變里彼城。對(duì)象的引用存在虛擬機(jī)棧，棧幀也存放在虛擬機(jī)棧退个，其實(shí)也就是通常理解的棧內(nèi)存募壕，每個(gè)棧幀都有自己的局部變量表≈钠颍可以這么理解司抱，對(duì)象的引用劫持了對(duì)象，指向了對(duì)象在堆內(nèi)存中的首地址黎烈，通過等于號(hào)賦值的都是引用傳遞习柠，但是棧幀中的那個(gè)「參數(shù)」沒有改變堆內(nèi)存的權(quán)利匀谣，如果要改變它指向的對(duì)象，只能自己重新創(chuàng)建一塊內(nèi)存资溃。
每當(dāng)一個(gè)java方法被執(zhí)行時(shí)都會(huì)在虛擬機(jī)中新創(chuàng)建一個(gè)棧幀武翎，方法調(diào)用結(jié)束后即被銷毀。
棧幀存儲(chǔ)空間為虛擬機(jī)棧溶锭，每一個(gè)棧幀都有自己的局部變量表宝恶、操作數(shù)棧和指向當(dāng)前方法所屬的類的運(yùn)行時(shí)常量池的引用。
在每個(gè)線程中趴捅，只有目前正在執(zhí)行的那個(gè)方法的棧幀是活動(dòng)的垫毙。這個(gè)棧幀就稱為當(dāng)前棧幀（current frame），這個(gè)棧幀對(duì)應(yīng)的方法稱之為當(dāng)前方法（current method）拱绑。定義這個(gè)方法的類就稱之為當(dāng)前類（current class）综芥。對(duì)局部變量表和操作數(shù)棧的各種操作，通常都指的是對(duì)當(dāng)前棧幀的局部變量表和操作數(shù)棧進(jìn)行的操作猎拨。如下圖所示膀藐，
如果用全局變量，就不會(huì)有這種問題了红省。
我感覺我真的有點(diǎn)鉆牛角尖了额各。。
貼一個(gè)我的回答：
https://www.zhihu.com/question/27764932/answer/272648864
ref:
https://www.cnblogs.com/editice/p/5420716.html
http://blog.csdn.net/zgrjkflmkyc/article/details/8774511
