226. Invert Binary Tree
Problem description:
Invert a binary tree.
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1
Solution
The basic idea is to swap the left and right node of the root. We can use recursive or non-recursive method to solve this question.
recursive method
1
2
3
4
5
6
7
8TreeNode* invertTree(TreeNode* root) {
if (root) {
invertTree(root->left);
invertTree(root->right);
std::swap(root->left, root->right);
}
return root;
}non-recursive method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28/**
* 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) {
//use non-recursive method
stack<TreeNode*> stk;
stk.push(root);
//stack: last in first out
while(!stk.empty()){
TreeNode* p= stk.top();
stk.pop();
if(p){
stk.push(p->left);
stk.push(p->right);
swap(p->left, p->right);
}
}
return root;
}
};