Hello, 大家好，今天是我参加 9 月更文的第 8 天，今天给大家带来的关于二叉树相关的算法题是二叉树的左叶子之和，正文如下：
题目
翻转一棵二叉树。
示例：
输入：
输出：
解题思路
根据题意，翻转二叉树的意思就是把每个节点的左右孩子翻转，这样就可以达到整体的翻转效果了。
所以，我们可以利用先序遍历，中序遍历，后续遍历这三种方法中的一种来实现翻转，思路如下：
递归三部曲：
确定递归函数的参数和返回值：递归函数的参数为输入的节点，由于题目中需要返回 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 root; } }
复制代码
最后
复杂度分析：
评论