反转二叉树 Posted on 2021-06-11 00:00:00 2021-06-26 00:00:00 by Author 摘要 给一棵二叉树，你能反转这颗二叉树吗(除了递归，还能使用其他的方法吗？) # 反转二叉树 > 写于2021/06/11 1. 题目描述 - 给定一颗二叉树，你能反转这颗二叉树吗？ 2. 代码示例 - 示例一 - 输入：  - 输出：  - 示例二： - 输入：  - 输出：  3. 解题思路 - 这道题是比较简单的，首先我们知道对于一个不为空的节点，交换它的左右孩子节点就可以了，左右孩子下面所有的节点顺带平移了位置，他们内部的位置可木有改变，这只是改变该节点下左右孩子的位置，然后我们用递归的方式，逐个用该方法去改变该节点下孩子节点的位置。用递归的方式可以用前序遍历或者后续遍历的方式，只是在递归前先交换该节点下的左右孩子即可。具体代码见如下代码。 - 之前讲了用迭代法实现二叉树的前后序遍历，那这里我们也可以使用迭代法完成二叉树的反转，这里拿二叉树前序遍历的迭代法举例，后序遍历的方式类似。我们知道，在前序遍历的时候，一个节点出栈的时候，先加入右孩子，然后在加入左孩子，以便下次继续遍历与操作，那么我们在该节点出栈的时候，先交换该节点的左右孩子，然后让右孩子进栈和让左孩子进栈，这样就能实现二叉树的反转了。其实思想和递归方式一样，就是在进行下一步遍历的时候，先进行交换左右孩子的位置即可。具体代码见迭代的写法。 4. 代码实现 ```java //递归写法 public TreeNode invertTree(TreeNode root) { //定义一个临时节点，因为在交换节点的时候，需要一个节点来临时保存 TreeNode temp; //如果该节点不为空 if (root != null) { //交换左右孩子 temp = root.left; root.left = root.right; root.right = temp; //递归方式遍历左右孩子 invertTree(root.left); invertTree(root.right); } //返回最终将结果 return root; } ``` ```java //前序遍历迭代的写法 public TreeNode invertTree(TreeNode root) { //定义两个临时节点，一个在交换节点的时候，需要一个节点来临时保存 //另一个在栈弹出来的时候需要使用 TreeNode temp1, temp2; //如果根节点为空，直接返回 if (root == null) { return root; } //定义一个节点类型的栈 Stack<TreeNode> stack = new Stack<>(); //首先把根节点压入栈中，以便后续的操作 stack.add(root); while (!stack.isEmpty()) { //首先保存出栈的节点到一个临时变量里 temp1 = stack.pop(); //下面三步是交换左右孩子的步骤 temp2 = temp1.left; temp1.left = temp1.right; temp1.right = temp2; //交换后，按照前序遍历的方式，加入右孩子到栈中(如果右孩子存在) if (temp1.right != null) { stack.add(temp1.right); } //交换后，按照前序遍历的方式，加入左孩子到栈中(如果左孩子存在) if (temp1.left != null) { stack.add(temp1.left); } } //返回最终将结果 return root; } ```
{{ item.content }}
{{ child.content }}