二叉树的镜像
题目描述
请完成一个函数,输入一个二叉树,该函数输出它的镜像。
例如输入:
1 2 3 4 5
| 4 / \ 2 7 / \ / \ 1 3 6 9
|
镜像输出:
1 2 3 4 5
| 4 / \ 7 2 / \ / \ 9 6 3 1
|
示例
1 2
| 输入:root = [4, 2, 7, 1, 3, 6, 9] 输出:[4, 7, 2, 9, 6, 3, 1]
|
题目来源:力扣(LeetCode)
题目链接:https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof
题目著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法一
利用二叉树的递归特性,直接递归地来交换每个节点即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
class Solution { public TreeNode mirrorTree(TreeNode root) { swap(root); return root; }
public void swap(TreeNode root) { if (root == null) return; TreeNode temp = root.left; root.left = root.right; root.right = temp; mirrorTree(root.left); mirrorTree(root.right); } }
|
解法二
利用深度优先遍历来访问二叉树中的节点,在访问这些节点时,交换他们的左右子树。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
|
class Solution { public TreeNode mirrorTree(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); if (root != null) stack.push(root); while (!stack.empty()) { TreeNode rootNode = stack.pop(); TreeNode leftNode = rootNode.left; TreeNode rightNode = rootNode.right; if (leftNode != null) stack.push(leftNode); if (rightNode != null) stack.push(rightNode); rootNode.left = rightNode; rootNode.right = leftNode; } return root; } }
|
解法三
也可以使用广度优先遍历来遍历二叉树。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
|
class Solution { public TreeNode mirrorTree(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); if (root != null) queue.offer(root); while (queue.size() != 0) { TreeNode rootNode = queue.poll(); TreeNode leftNode = rootNode.left; TreeNode rightNode = rootNode.right; if (leftNode != null) queue.offer(leftNode); if (rightNode != null) queue.offer(rightNode); rootNode.left = rightNode; rootNode.right = leftNode; } return root; } }
|