##題目描述 輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表，要求不能創建任何新的結點，只能調整樹中結點指標的指向，
思路
關于樹的深度搜索操作，一般都有遞回和堆疊兩種實作，
此題對樹進行中序遍歷，在遍歷程序中操作前后兩個結點，所以需要pre指標，
時間復雜度O(n)，空間復雜度O(1)，
正確的遞回代碼
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private TreeNode pre;
private void helper(TreeNode curr) {
if(curr == null) return ;
helper(curr.left);
curr.left = pre;
if(pre != null) {
pre.right = curr;
}
pre = curr;
helper(curr.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) return null;
helper(pRootOfTree);
TreeNode p = pRootOfTree;
// 類似非遞回代碼，設定一個成員變數可以無需回圈查找
while(p.left != null) {
p = p.left;
}
return p;
}
}
錯誤的遞回代碼
public class Solution {
private void helper(TreeNode pre, TreeNode curr) {
if(curr == null) return ;
helper(pre, curr.left);
curr.left = pre;
if(pre != null) {
pre.right = curr;
}
pre = curr;
helper(pre, curr.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) return null;
helper(null, pRootOfTree);
TreeNode p = pRootOfTree;
while(p.left != null) {
p = p.left;
}
return p;
}
}
非遞回代碼
import java.util.Stack;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) return null;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode first = null;
TreeNode p = pRootOfTree;
TreeNode pre = null;
while(p != null || !stack.empty()) {
while(p != null) {
stack.push(p);
p = p.left;
}
p = stack.pop();
if(pre != null) {
p.left = pre;
pre.right = p;
pre = p;
} else {
p.left = null;
pre = p;
first = p;
}
p = p.right;
}
return first;
}
}
筆記
錯誤遞回代碼主要是遞回攜帶的pre引數受到了運行時堆疊幀的影響，先壓入的堆疊幀無法感知到后壓入堆疊幀對pre的修改，所以在堆疊幀彈出時，后彈出的堆疊幀使用的依舊是舊的pre引數，但整個遞回函式的運行，per引數是需要在遞回每一層更新的，也就是說先入堆疊的堆疊幀將pre引數傳遞給后面入堆疊的堆疊幀，同時先彈出的堆疊幀，需要將修改后的pre同步給還未彈出的堆疊幀，參考傳遞并沒有這個效果，所以雖然pre是參考傳遞，但每一個堆疊幀在運行時，使用的仍是當初保存的舊的參考，
參考傳遞保證的是不同變數指向同一記憶體（區別于C++的參考）
所以這里需要使用成員變數，使每一個堆疊幀操作的都是同一個pre，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85173.html
標籤：其他
上一篇：復雜鏈表的復制
下一篇：Escape（反思與總結）