Leetcode : 0226. Invert Binary Tree (Tree)

tags:leetcode

DFS normal method

/**
 * 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==NULL)
            return root;
        else{
            invertTree(root->left); // add left depth
            invertTree(root->right); // add right depth
            swap(root->left, root->right); //swap it
            return root;
        }
    }
};

DFS(preorder traversal)

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL)
            return root;
        else{
            stack<TreeNode*>s; //FILO
            s.push(root);
            while(!s.empty()){
                TreeNode* tmp=s.top();
                s.pop();
                swap(tmp->left, tmp->right);
                if(tmp->left)
                    s.push(tmp->left);
                if(tmp->right)
                    s.push(tmp->right);
            }
        }
        return root;
    }
};

BFS method

/**
 * 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 == NULL){
            return root;
        } else {
            queue <TreeNode*> q; //FIFO
            q.push(root);
            while(!q.empty()){
                q.pop();
                swap(q->left,q->right);
                if(q->left) q.push(q->left);
                if(q->right) q.push(q->right);
            }
        }
        return root;
    }
};
//BFS time limited.
//this DFS better it.