高端定制网站建设,金融行业网站建设公司,网站建设狼盾网络,深圳网站seo推广问题描述
给定一个二叉树#xff0c;将其每个节点的左右子树进行反转。
解决方案
以下是 C 代码实现#xff1a;
TreeNode* invertTree(TreeNode* root) {if (root nullptr) {return nullptr;}// 交换当前节点的左右子树TreeNode* temp root-left;root-left r…问题描述
给定一个二叉树将其每个节点的左右子树进行反转。
解决方案
以下是 C 代码实现
TreeNode* invertTree(TreeNode* root) {if (root nullptr) {return nullptr;}// 交换当前节点的左右子树TreeNode* temp root-left;root-left root-right;root-right temp;// 递归反转左右子树invertTree(root-left);invertTree(root-right);return root;
}
代码解释
如果当前节点为空则直接返回 nullptr。交换当前节点的左右子树。递归地对左子树和右子树进行相同的操作。返回当前节点作为新的根节点。
递归和迭代方法
上述解决方案使用了递归方法它是简洁且易于理解的。然而也可以使用迭代方法来反转二叉树通常使用队列或栈来实现。
以下是使用队列进行迭代的 C 代码示例
TreeNode* invertTreeIterative(TreeNode* root) {if (root nullptr) {return nullptr;}queueTreeNode* q;q.push(root);while (!q.empty()) {TreeNode* current q.front();q.pop();// 交换当前节点的左右子树TreeNode* temp current-left;current-left current-right;current-right temp;// 将子节点加入队列if (current-left ! nullptr) {q.push(current-left);}if (current-right ! nullptr) {q.push(current-right);}}return root;
}在迭代方法中我们使用一个队列来存储那些需要交换子节点的树节点。在队列不为空的情况下我们不断地从队列中取出节点交换它们的左右子节点然后将它们的子节点如果存在的话加入队列中继续处理。这个过程会持续到队列为空即所有节点都被处理过为止。
