网站排名优化提升快速,如何做网页公证,资海网站建设,怎么搭建个人博客声明
该系列文章仅仅展示个人的解题思路和分析过程#xff0c;并非一定是优质题解#xff0c;重要的是通过分析和解决问题能让我们逐渐熟练和成长#xff0c;从新手到大佬离不开一个磨练的过程#xff0c;加油#xff01;
原题链接
翻转二叉树备战技术面试#xff1f;…声明
该系列文章仅仅展示个人的解题思路和分析过程并非一定是优质题解重要的是通过分析和解决问题能让我们逐渐熟练和成长从新手到大佬离不开一个磨练的过程加油
原题链接
翻转二叉树备战技术面试力扣提供海量技术面试资源帮助你高效提升编程技能轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/invert-binary-tree/
算法分析 如下图1和图2可按照1、2、3、4的顺序依次对每个非叶子节点的左右孩子节点进行镜像反转对于只有一个孩子节点的节点也要进行镜像反转操作。 图1 图2 分析 1.如何完成镜像反转 可以通过递归遍历整棵树遍历过程中按照以下方式进行判断和操作 1若当前节点为空或无左孩子和右孩子节点则return; 2否则继续遍历左右孩子节点; 3交换左右孩子节点; 2.如何交换左右孩子节点 1左右孩子节点均不为空则交换左右孩子节点 2左孩子节点为空右孩子节点不为空则左孩子节点右孩子节点右孩子节点置空 3右孩子节点为空左孩子节点不为空则右孩子节点左孩子节点左孩子节点置空.
代码示例C#
//翻转二叉树
public TreeNode MirrorTree(TreeNode root)
{if (root ! null) Reverse(root);return root;
}//对以指定节点为根节点的二叉树进行镜像反转操作
private void Reverse(TreeNode node)
{//检测是否满足镜像反转要求if (node null || (node.left null node.right null)) return;if (node.left ! null) Reverse(node.left);//对当前节点的左孩子节点进行镜像反转操作if (node.right ! null) Reverse(node.right);//对当前节点的右孩子节点进行镜像反转操作SwapChildren(node);//交换当前节点的左右孩子节点
}//交换指定节点的左右孩子节点
private void SwapChildren(TreeNode node)
{if (node.left ! null node.right ! null)(node.left, node.right) (node.right, node.left);else if (node.left null node.right ! null)(node.left, node.right) (node.right, null);else if (node.left ! null node.right null)(node.right, node.left) (node.left, null);
}
算法解说 根据题目要求我们需要对一个二叉树进行翻转操作主方法的输入是该二叉树的根节点返回值也是一个节点。实际上我们可以对问题进行细分对二叉树的翻转实际上就是对二叉树节点的交换或者说是将每个节点的位置进行重新排序有的节点的位置保持不变如根节点有的节点则需要与其它节点交换位置如叶子节点等。 对问题进行转换后我们自然需要对整个二叉树进行遍历那么我们就需要搞清楚两个问题。 1.什么时候交换节点 2.怎么交换节点 如图1和图2我们列举出了本题目将会出现的两种二叉树根据这两种二叉树我们去找到上面两个问题的答案具体思路请参考算法分析。 如何将算法分析转换为代码依旧是确定两个点一是变量二是逻辑主体本题目的算法分析中并没有要求需要单独定义变量去记录数据所以我们只看逻辑主体即可代码示范中我们将节点交换方法独立出来以方便维护以及增加可读性由于我们采用的是递归方式遍历二叉树所以进行二叉树反转的逻辑我们也将其单独定义为一个函数。
