【树】226. 翻转二叉树

226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

     4
   /  \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

DFS

swap函数可以直接调换两个指针的指向

void change(TreeNode* p){
        if(p){
            swap(p->left,p->right);
            change(p->left);
            change(p->right);
        }
    }
    TreeNode* invertTree(TreeNode* root) {
        change(root);
        return root;
    }

BFS

用BFS利用迭代，在根元素出队列的时候将两子节点调换，再依次入队

TreeNode* invertTree(TreeNode* root) {
      if(!root) return NULL;
      queue<TreeNode*> q;
      q.push(root);
      while(!q.empty()){
          int size = q.size();
          for(int i=0;i<size;i++){
              TreeNode* tmp =  q.front();
              q.pop();
              if(tmp){
                  swap(tmp->left, tmp->right);
                  q.push(tmp->left);
                  q.push(tmp->right);
              }
          }
      }
      return root;
}