大前端

前端学习之家-大前端

【LeetCode】226.翻转二叉树

文章目录

  • 问题描述
  • 法I:层序遍历实现翻转
  • 法II:递归

问题描述

翻转一棵二叉树。

示例:

输入:

     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出:

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

备注:
这个问题是受到 Max Howell 的 原问题 启发的 :

谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

法I:层序遍历实现翻转

//翻转二叉树
class Solution {
public:
	TreeNode* invertTree(TreeNode* root) {
		if (root == nullptr) {
			return root;
		}
		queue<TreeNode*> q;
		q.push(root);
		while (!q.empty()) {
			auto cur = q.front();
			q.pop();
			auto l = cur->left;
			auto r = cur->right;
			cur->left = r;
			cur->right = l;
			if (cur->left != nullptr) {
				q.push(cur->left);
			}
			if (cur->right != nullptr) {
				q.push(cur->right);
			}
		}
		return root;
	}
};

在这里插入图片描述

法II:递归

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};

在这里插入图片描述

发表评论:

Copyright Your WebSite.Some Rights Reserved.