【leetcode】226. Invert Binary Tree(easy)

Invert a binary tree.
输入

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

输出

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

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

反转二叉树

代码中多加了构建二叉树和打印二叉树的方法。用来测试。

void printTree(TreeNode* root)
{
	if (root)
	{
		std::cout << root->val << " ";
		printTree(root->left);
		printTree(root->right);
	}
}

void createTreeTravel(TreeNode *root, vector<int> &list, int index)
{
	if (index * 2 + 1 < list.size())
	{
		root->left = new TreeNode(list[index * 2 + 1]);
		createTreeTravel(root->left, list, index * 2 + 1);
	}
	if (index * 2 + 2 < list.size())
	{
		root->right = new TreeNode(list[index * 2 + 2]);
		createTreeTravel(root->right, list, index * 2 + 2);
	}
}



TreeNode* createTree(vector<int> list)
{
	TreeNode* root = new TreeNode(list[0]);
	createTreeTravel(root, list, 0);
	return root;
}


void travelTree(TreeNode* & left, TreeNode* & right)
{
	TreeNode* t = right;
	right = left;
	left = t;

	if (left)
	{
		travelTree(left->left, left->right);
	}

	if (right)
	{
		travelTree(right->left, right->right);
	}
}

// 226. Invert Binary Tree
TreeNode* Solution::invertTree(TreeNode* root)
{
	if (root == NULL) return root;
	travelTree(root->left, root->right);
	return root;
}

// 测试代码
vector<int> list{1, 2, 3, 4, 5, 6};
TreeNode* root = createTree(list);
printTree(root);
std::cout << endl;

TreeNode* t = invertTree(root);
printTree(t);
std::cout << endl;

1 2 4 5 3 6
1 3 6 2 5 4

Runtime: 4 ms, faster than 100.00% of C++ online submissions for Invert Binary Tree.
Memory Usage: 9.2 MB, less than 58.59% of C++ online submissions for Invert Binary Tree.