LeetCode演算法題-Invert Binary Tree
這是悅樂書的第194 次更新,第199 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第55題(順位題號是226)。反轉二叉樹。例如:
輸入:
4 / \ 27 / \ / \ 13 69
輸出:
4 / \ 72 / \ / \ 96 31
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
二叉樹的任意一個節點進行反轉操作時,當前節點還是當前節點,當前節點的左子節點變成右子節點,當前節點的右子節點變成左子節點。也就是下面的三行核心程式碼:
TreeNode temp = root.left; root.left = root.right; root.right = temp;
如果從根節點開始,那麼先把根節點的左右子節點互換,然後利用遞迴,再將已經互換了的左右子節點他們自身的左右子節點進行互換,最後返回root。
public TreeNode invertTree(TreeNode root) { if (root == null || (root.left == null && root.right == null)) { return root; } TreeNode temp = root.left; root.left = root.right; root.right = temp; root.left = invertTree(root.left); root.right = invertTree(root.right); return root; }
03 第二種解法
此解法比上面的第一種解法精簡了些,直接將上面核心程式碼進行套用,將root的左子節點取出存入tmp,再將root的左子節點指向遞迴後的root的右子節點,再將root的右子節點指向遞迴後的tmp,最後返回root即可。
public TreeNode invertTree2(TreeNode root) { if (root == null || (root.left == null && root.right == null)) { return root; } TreeNode tmp = root.left; root.left = invertTree2(root.right); root.right = invertTree2(tmp); return root; }
04 第三種解法
利用佇列,藉助其先進先出的特性。在進行迴圈進佇列、出佇列的操作時,核心程式碼還是最開始那三行程式碼,進行左右子節點互換。
public TreeNode invertTree3(TreeNode root) { TreeNode r = root; Queue<TreeNode> q = new LinkedList<TreeNode>(); if (root != null) { q.add(root); } while (!q.isEmpty()) { TreeNode curr = q.remove(); TreeNode temp = curr.left; curr.left = curr.right; curr.right = temp; if (curr.left != null) { q.add(curr.left); } if (curr.right != null) { q.add(curr.right); } } return r; }
05 小結
演算法專題目前已連續日更超過一個月,演算法題文章55 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!