LeetCode 226翻转二叉树 LeetCode

LeetCode 226翻转二叉树

题目简述：翻转一棵二叉树。
输入：[4, 2, 7, 1, 3, 6, 9] 输出：[4, 7, 2, 9, 6, 3, 1]
思路：递归遍历整棵二叉树，遍历到每个节点时交换左右儿子。时间复杂度O(n)

class Solution { public: TreeNode* invertTree(TreeNode* root) { if(!root) return 0; swap(root->left, root->right); invertTree(root->left); invertTree(root->right); return root; } };

思路：利用栈或者队列迭代

//栈写法 class Solution { public: TreeNode* invertTree(TreeNode* root) { if(!root) return 0; stack s; s.push(root); while(s.size()) { TreeNode* cur = s.top(); //swap(cur->left, cur->right); //等价于下面三行 TreeNode* tmp = cur->right; cur->right = cur->left; cur->left = tmp; s.pop(); if(cur->left) s.push(cur->left); if(cur->right) s.push(cur->right); } return root; } }; //队列写法 class Solution { public: TreeNode* invertTree(TreeNode* root) { if(!root) return 0; queue q; q.push(root); while(q.size()) { TreeNode* cur = q.front(); swap(cur->left, cur->right); q.pop(); if(cur->left) q.push(cur->left); if(cur->right) q.push(cur->right); } return root; } };