LeetCode演算法題-Convert BST to Greater Tree(Java實現)
這是悅樂書的第255 次更新,第268 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第122題(順位題號是538)。給定二進位制搜尋樹(BST),將其轉換為更大樹,使原始BST的每個鍵都更改為原始鍵加上所有鍵的總和大於BST中的原始鍵。例如:
輸入:二進位制搜尋樹的根,如下所示:
5 / \ 213
輸出:大樹的根,如下所示:
18 / \ 20 13
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
題目的意思是將一個二叉搜尋樹的節點按照右根左的順序累加,用不斷累加的值作為原節點新的節點值,至於返回後新的二叉樹,題目並沒有要求是二叉搜尋樹,因此我們可以直接使用遞迴方法,順序為右根左,另外還需要定義一個全域性變數sum,來依次累加節點值。
此解法的時間複雜度是O(n),空間複雜度是O(n)。
private int sum = 0; public TreeNode convertBST(TreeNode root) { if (root == null) { return null; } convertBST(root.right); sum += root.val; root.val = sum; convertBST(root.left); return root; }
03 第二種解法
我們還可以使用迭代的方法來解,藉助棧(或者佇列)來實現。先將當前節點的所有右子節點進棧,然後出棧一個節點,此節點是最下面一層的第一個右子節點,然後節點值開始累加,然後再將左子節點依次進棧。
此解法的時間複雜度是O(n),空間複雜度是O(n)。
public TreeNode convertBST2(TreeNode root) { if (root == null) { return null; } int sum = 0; Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode node = root; while (!stack.isEmpty() || node != null) { while (node != null) { stack.push(node); node = node.right; } node = stack.pop(); sum += node.val; node.val = sum; node = node.left; } return root; }
04 第三種解法
還有一種比較厲害的解法,Reverse Morris In-order Traversal(逆向莫里斯有序遍歷),是由一個叫Morris的人提出的,感興趣的可以去仔細研究下。
此解法的時間複雜度是O(n),空間複雜度是O(1)。
public TreeNode convertBST3(TreeNode root) { TreeNode cur = root; int sum = 0; while (cur != null) { if (cur.right == null) { sum += cur.val; cur.val = sum; cur = cur.left; } else { TreeNode prev = cur.right; while (prev.left != null && prev.left != cur) { prev = prev.left; } if (prev.left == null) { prev.left = cur; cur = cur.right; } else { prev.left = null; sum += cur.val; cur.val = sum; cur = cur.left; } } } return root; }
05 小結
演算法專題目前已日更超過三個月 ,演算法題文章122 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!