翻转二叉树,通过前序遍历的顺序,从根节点开始,将节点的左右子节点一次进行交换即可。
/*** 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 == nullptr){return root;}TreeNode* temp = root->left;root->left = root->right;root->right = temp;invertTree(root->left);invertTree(root->right);return root;}
};
使用迭代的统一写法,前序遍历代码如下:
class Solution {
public:TreeNode* invertTree(TreeNode* root) {stack<TreeNode*> st;if(root != nullptr){st.push(root);}while(!st.empty()){TreeNode* cur = st.top();st.pop();if(cur != nullptr){//st.pop();if(cur->right != nullptr) {st.push(cur->right);}if(cur->left != nullptr) {st.push(cur->left);}st.push(cur);st.push(nullptr);} else {//st.pop();TreeNode * cur = st.top();st.pop();swap(cur->left, cur->right);}}return root;}
};