手撸二叉树之翻转二叉树

手撸二叉树之翻转二叉树

今天给大家带来的关于二叉树相关的算法题是翻转二叉树，正文如下：

题目

翻转一棵二叉树。

示例：

输入：

4 / \ 2 7 / \ / \1 3 6 9

输出：

4 / \ 7 2 / \ / \9 6 3 1

解题思路

根据题意，翻转二叉树的意思就是把每个节点的左右孩子翻转，这样就可以达到整体的翻转效果了。

所以，我们可以利用先序遍历，中序遍历，后续遍历这三种方法中的一种来实现翻转，思路如下：

递归三部曲：

确定递归函数的参数和返回值：递归函数的参数为输入的节点，由于题目中需要返回 TreeNode 类型的返回值，所以递归函数的返回值为 TreeNode;确定终止条件：当 root == null 时,终止递归，返回 root;确定单层递归逻辑: 如果是先序遍历，则先交换左右孩子节点，然后翻转左子树，再翻转右子树；如果是中序遍历，则先翻转左子树，再交换左右孩子节点，最后翻转右子树；如果是后序遍历，则先翻转左子树，再翻转右子树，最后交换左右孩子节点；

代码实现

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */// 利用前序遍历class Solution { // 先序遍历--从顶向下交换 public TreeNode invertTree(TreeNode root) { if (root == null) return null; // 保存右子树 TreeNode rightTree = root.right; // 交换左右子树的位置 root.right = invertTree(root.left); root.left = invertTree(rightTree); return root; } }// 利用中序遍历class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) return null; invertTree(root.left); // 递归找到左节点 TreeNode rightNode= root.right; // 保存右节点 root.right = root.left; root.left = rightNode; // 递归找到右节点 继续交换 : 因为此时左右节点已经交换了,所以此时的右节点为root.left invertTree(root.left); }}// 利用后序遍历 class Solution { public TreeNode invertTree(TreeNode root) { // 后序遍历 if (root == null) return null; TreeNode leftNode = invertTree(root.left); TreeNode rightNode = invertTree(root.right); root.right = leftNode; root.left = rightNode; return

最后

复杂度分析：

时间复杂度：O(N)，其中 N 为二叉树节点的数目。空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。