Invert a binary tree.
4 / 2 7 / \ / 1 3 6 9
to
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 fuck off.
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
递归版：
struct TreeNode* invertTree(struct TreeNode* root) { struct TreeNode *node; if (root == NULL) return root; node = invertTree(root->left); root->left = invertTree(root->right); root->right = node; return root; }
非递归版：
struct TreeNode* invertTree(struct TreeNode *root) { struct TreeNode *node, *tmp; Stack treeStack; if (root == NULL) return root; stack_init(&treeStack, NULL); stack_push(&treeStack, root); while (treeStack.size > 0) { stack_pop(&treeStack, &node); tmp = node->left; node->left = node->right; node->right = tmp; if (node->left) stack_push(&treeStack, node->left); if (node->right) stack_push(&treeStack, node->right); } stack_destory(&treeStack); return root; }
原文：http://www.cnblogs.com/codelu/p/4590844.html