编号226:翻转二叉树
翻转一棵二叉树。
思路:
要实现反转,就是要把每个结点的左右孩子交换一下(孩子下面的结点是一起交换的),需要的是遍历的顺序,递归的中序遍历的方法不可以实现,因为会交换两次。
//利用前序遍历递归实现
public static Node reverseTree(Node root){
if(root == null){
return null;
}
swap(root.left,root.right);//中
reverseTree(root.left);//左
reverseTree(root.right);//右
return root;
}
//利用迭代实现
public static Node reverseTree2(Node root){
if(root == null){
return root;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
//交换左右子树
Node node = stack.pop();
Node temp = node.left;
node.left = node.right;
node.right=temp;
if(node.left != null){
stack.push(node.left);
}
if(node.right!=null){
stack.push(node.right);
}
}
return root;
}
//利用层序遍历使用
public Node levelOrder(Node root) {
if (root == null) {
return null;
}
//创建优先级队列
Queue<Node> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
while (size-->0){
//将当前元素的非空子节点压入队列
Node temp = queue.poll();
swap(temp.left,temp.right);
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
}
}
return root;
}