怀化找什么人做网站,店面设计公司,做网站注册页面模板,网站建设添加汉语本文主要讲解反转二叉树的要点与细节#xff0c;按照步骤思考更方便理解
c和java代码如下#xff0c;末尾 给你一棵二叉树的根节点 root #xff0c;翻转这棵二叉树#xff0c;并返回其根节点。 具体要点#xff1a;
1. 首先我们要理解题意#xff0c; 反转二叉树具体… 本文主要讲解反转二叉树的要点与细节按照步骤思考更方便理解
c和java代码如下末尾 给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 具体要点
1. 首先我们要理解题意 反转二叉树具体来说就是针对每个节点交换他们左右子节点的指针而不是交换数值 2. 既然是涉及到交换那么就是需要swap函数或者是temp临时变量如下 swap(root-left, root-right); //交换左右子树的指针 3. 其次涉及到二叉树我们第一时间就要想到二叉树的遍历顺序以及递归或是遍历操作。文章末尾会具体分析什么时候用哪种方式。 本题我们优先使用前序遍历递归操作不了解二叉树遍历顺序的可以参考这个文章 前序中 左 右 递归递归参数与返回值 终止条件 单层递归逻辑 4. 接下来我们具体考虑递归应该怎么写 首先递归参数与返回值 递归传入的参数是我们每次的节点返回的也是我们传入的节点 TreeNode* invertTree(TreeNode* root) 其次确定终止条件 对于二叉树来说终止条件一般是遇到节点是null就终止并返回 if (root nullptr)return root; 最后确定单层递归逻辑 在2中我们已经分析了要交换左右子树的指针接下来我们就要继续递归左右子树 //递归操作交换左右子树
swap(root-left, root-right);
//左子树
invertTree(root-left);
//右子树
invertTree(root-right); 5. 最后总结
在二叉树的遍历中我们通常使用不同的数据结构来模拟递归过程或实现特定的遍历顺序层序遍历。
通常来说前中后序遍历——递归层序遍历——队列模拟广度优先遍历
但是前中后序遍历也可以用迭代法实现——栈模拟深度优先遍历 c代码如下
class Solution {
public:TreeNode* invertTree(TreeNode* root) {//递归前序遍历中左右//递归终止条件if (root nullptr)return root;//递归操作交换左右子树swap(root-left, root-right);//左子树invertTree(root-left);//右子树invertTree(root-right);return root;}
};
java代码如下
class Solution {public TreeNode invertTree(TreeNode root) {if(root null) return null;TreeNode temproot.left;root.leftroot.right;root.righttemp;invertTree(root.left);invertTree(root.right);return root;}
}
