[LeetCode]Invert Binary Tree

Invert a binary tree.

4 / \ 27 / \ / \1 3 6 9to4 / \ 72 / \ / \9 6 3 1Trivia:This problem was inspired bythis original tweetbyMax 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; *TreeNode *left; *TreeNode *right; *TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:TreeNode* invertTree(TreeNode* root) {TreeNode *res = root;recursion(root);return res;}void recursion(TreeNode *root){if(root==NULL)return;TreeNode *temp = root->left;root->left = root->right;root->right = temp;invertTree(root->left);invertTree(root->right);}};

非递归

/** * Definition for a binary tree node. * struct TreeNode { *int val; *TreeNode *left; *TreeNode *right; *TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:TreeNode* invertTree(TreeNode* root) {if(root==nullptr)return nullptr;stack<TreeNode*> stk;TreeNode *res = root;stk.push(root);while(!stk.empty()){TreeNode* node = stk.top();stk.pop();if(node->left||node->right){ //非叶节点TreeNode* temp = node->left;node->left = node->right;node->right = temp;}if(node->left)//注意空指针stk.push(node->left);if(node->right)stk.push(node->right);}return res;}};

思念是一种幸福的忧伤，是一种甜蜜的惆怅，是一种温馨的痛苦；