算法题--反转二叉树 2022-02-15 10:44 > 好几次面试都问到过，问二叉树基本必问反转。 BFS（Breadth First Search）广度（宽度）优先搜索 DFS（Depth First Search）深度优先搜索 三种方法：递归、栈、队列 递归反转思想很简单：先反转当前节点（当前节点不能为空，所以开头要先判断），再反转左节点，最后反转右节点（由于当前方法就是反转节点的方法，所以反转左右节点就调用当前方法即可）。 栈和队列则是使用循环来控制将所有节点反转完成。 其中由于方式不同，反转的过程也不同，递归肯定是深度优先（DFS），栈由于是先进后出，所以也是深度优先（DFS）；队列先进先出，所以是广度优先（BFS）。 三种方式实现： ```java package com.example.demo.core.Leecode; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /** * @author: HanXu * on 2022/2/15 * Class description: 反转二叉树 */ public class ReversalBinaryTree { static class Node { int element; Node left; Node right; public Node(int element) { this.element = element; } } public static void main(String[] args) { //先序创建一个二叉树 Node node = buildTree(); printTree(node); System.out.println(); //反转二叉树 reverTree(node); // reverTree2(node); // reverTree3(node); //输出二叉树 printTree(node); /* 1 2 3 4 5 6 7 8 9 10 1 6 8 10 9 7 2 3 5 4 */ } /** * 反转二叉树 使用队列 BFS 广度优先 * 因为队列是先进先出的，从根节点开始，先进的总是左右子节点，所以先反转的也是左右子节点，总是会将当前层级全部反转之后才反转下一层节点 * 且由于存入队列之前已经交换了左右子树，所以总是从右子树开始反转到左子树，按照这样层层向下推进 * 反转节点顺序：1 6 2 8 7 3 10 9 5 4 * @param rootNode */ public static void reverTree3(Node rootNode) { if (rootNode == null) { return; } Queue<Node> queue = new LinkedList<>(); queue.offer(rootNode); while (!queue.isEmpty()) { //交换当前节点的左右子节点 Node node = queue.poll(); Node left = node.left; node.left = node.right; node.right = left; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } } /** * 反转二叉树 使用栈 DFS 深度优先 * 因为栈是先进后出的，从根节点开始反转，反转左右，然后放入左右，最后根据先进后出，所以最终是先反转左子树；反转左子树时，左子树又有左右子节点，按照栈的特性，又会先出左节点，然后反转左右子树... * 所以一定是一直优先反转左子树，往最深处递进，到底了才开始反转右子树。 * 反转节点顺序：1 2 3 4 5 6 7 8 9 10 * @param rootNode */ public static void reverTree2(Node rootNode) { if (rootNode == null) { return; } //头结点入栈 Stack<Node> stack = new Stack<>(); stack.push(rootNode); //栈不空，就一直循环 while (!stack.isEmpty()) { Node node = stack.pop(); //交换当前节点的左右节点 Node left = node.left; node.left = node.right; node.right = left; if (node.left != null) { stack.push(node.left); } if (node.right != null) { stack.push(node.right); } } } /** * 反转二叉树，递归方式 * DFS 深度优先，因为是递归 * 反转节点顺序：1 6 8 10 9 7 2 3 5 4 * @param node */ public static void reverTree(Node node) { //临界条件 if (node == null) { return; } //先反转当前节点 Node leftNode = node.left; Node rightNode = node.right; node.left = rightNode; node.right = leftNode; //再反转左节点，再反转右节点 reverTree(node.left); reverTree(node.right); /* 1 2 3 4 5 6 7 8 9 10 1 6 8 10 9 7 2 3 5 4 */ } /** * 打印二叉树：先序遍历：先遍历根节点，再遍历左，再遍历右 * @param node */ public static void printTree(Node node) { if (node != null) { System.out.print(node.element + " "); printTree(node.left); printTree(node.right); } } /** * 构建二叉树。可以使用#代表空节点，结合数据结构能够写出较为优雅的创建方式，不是这节的重点，就不写了，以后补上。 * @return */ public static Node buildTree() { Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); Node node5 = new Node(5); Node node6 = new Node(6); Node node7 = new Node(7); Node node8 = new Node(8); Node node9 = new Node(9); Node node10 = new Node(10); node1.left = node2; node2.left = node3; node3.left = node4; node3.right = node5; node1.right = node6; node6.left = node7; node6.right = node8; node8.left = node9; node8.right = node10; return node1; } } /* 1 2 6 3 7 8 4 5 9 10 1 2 3 4 5 6 7 8 9 10 1 6 2 8 7 3 10 9 5 4 1 6 8 10 9 7 2 3 5 4 */ ``` --END--
发表评论