LeetCode-剑指offer27-二叉树镜像
题目
请完成一个函数,输入一个二叉树,该函数输出它的镜像。
例如输入:
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出:
4
/ \
7 2
/ \ / \
9 6 3 1
解法-递归
go代码实现如下:
func mirrorTree(root *TreeNode) *TreeNode {
if root == nil {
return root;
}
var node = mirrorTree(root.Left)
root.Left = mirrorTree(root.Right)
root.Right = node
return root
}
解法-非递归(栈)
辅助栈(或队列)
利用栈(或队列)遍历树的所有节点 nodenode ,并交换每个 nodenode 的左 / 右子节点。
算法流程:
- 特例处理: 当 rootroot 为空时,直接返回null ;
- 初始化: 栈(或队列),本文用栈,并加入根节点 root 。
- 循环交换: 当栈 stack 为空时跳出;
- 出栈: 记为 node ;
- 添加子节点: 将 node 左和右子节点入栈;
- 交换: 交换 node 的左 / 右子节点。
- 返回值: 返回根节点 root 。
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
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;
}
标题:LeetCode-剑指offer27-二叉树镜像
作者:guobing
地址:http://guobingwei.tech/articles/2020/10/25/1603621505470.html