【問題描述】[中等]

請完成一個函數，輸入一個二叉樹，該函數輸出它的鏡像。例如輸入：4/ \2 7/ \ / \ 1 3 6 9 鏡像輸出：4/ \7 2/ \ / \ 9 6 3 1示例 1：輸入：root = [4,2,7,1,3,6,9] 輸出：[4,7,2,9,6,3,1]

【解答思路】

1. 遞歸

時間復雜度：O(N) 空間復雜度：O(N)

class Solution {public TreeNode mirrorTree(TreeNode root) {if(root == null) return null;TreeNode tmp = root.left;root.left = mirrorTree(root.right);root.right = mirrorTree(tmp);return root;} } public TreeNode mirrorTree(TreeNode root) {if(root == null) return null;TreeNode leftRoot = mirrorTree(root.right);TreeNode rightRoot = mirrorTree(root.left);root.left = leftRoot;root.right = rightRoot;return root;}

2. 輔助棧（或隊列）

時間復雜度：O(N) 空間復雜度：O(1)

class Solution {public TreeNode mirrorTree(TreeNode root) {if(root == null) return null;Stack<TreeNode> stack = new Stack<>();stack.add(root);//Stack<TreeNode> stack = new Stack<>() {{ add(root); }};while(!stack.isEmpty()) {TreeNode node = stack.pop();if(node.left != null) stack.add(node.left);if(node.right != null) stack.add(node.right);TreeNode tmp = node.left;node.left = node.right;node.right = tmp;}return root;} }

【總結】

1.二叉樹鏡像的定義

2.二叉樹常見思路 ：遞歸 棧

3.學習其翻轉時暫存變量的思想 遞歸要有出口

轉載;https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/solution/mian-shi-ti-27-er-cha-shu-de-jing-xiang-di-gui-fu-/

總結

以上是生活随笔為你收集整理的[剑指offer][JAVA]面试题第[27]题[二叉树的镜像][递归][栈]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。