[LeetCode Road] Invert Binary Tree - Solution/C++

226. Invert Binary Tree

Question:

Given the root of a binary tree, invert the tree, and return its root.

Example:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Input: root = [2,1,3]
Output: [2,3,1]

Input:

root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 100].

-100 <= Node.val <= 100

Source code

Version 1

Idea:
It is a recursive method and likes DFS traversal of the tree. Implement swap() method between left node and right node.

Time complexity: O(n)
Space complexity: O(h) P.S. h is the height of the tree for the call stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root){
TreeNode* temp = root->left;
root->left = invertTree(root->right);
root->right = invertTree(temp);
}
return root;
}
};

Version 2

Idea:
The other way is Stack and similars to BFS traversal of the tree.

Time complexity: O(n)
Space complexity: O(n)

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
29
30
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
stack<TreeNode*> st;
st.push(root);

while(!st.empty()){
TreeNode* node = st.top();
st.pop();

if(node){
st.push(node->left);
st.push(node->right);
swap(node->left, node->right);
}
}
return root;
}
};