Binary Tree basic operations

In this blog, I am going to summarize the typical simple recursive operation of binary trees.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
including  height, traversals, invert. (will add more when I exercise others)

1. Invert a binary tree

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

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

    TreeNode* invertTree(TreeNode* root) { 
//end condition       
        if (!root) return nullptr;
//swap left right
        TreeNode* temp=root->left;
        root->left=root->right;
        root->right=temp;
//process children
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }

2.  Tree height

    int hTree(TreeNode* root) { 
       if (!root) return 0;
       return  1+max( hTree(root->left, root->right);
   }

3. Pre-order traversal

 vector<int> res;
 void  preOrder(TreeNode* root){
          if (!root) return ;
          res.push_back(root->val);
          preOrder(root->left);
          preOrder(root->right);

 }

4. In order

void  inOrder(TreeNode* root){
          if (!root) return ;         
          inOrder(root->left);
          res.push_back(root->val);
          inOrder(root->right);

 }

5. Post order

void  postOrder(TreeNode* root){
          if (!root) return ;         
          postOrder(root->left);
          postOrder(root->right);
          res.push_back(root->val);         

 }

6  level order (need BFS) . The following code return the vector of each level's values;

    vector<vector<int>> levelOrderBottom(TreeNode* root) {
       vector<vector<int>> res;
        if (!root) return res;
        queue <TreeNode*> q1,q2;
        q1.push(root);
        
        while (true){
            vector<int> vec;
            while (!q1.empty()){                
                TreeNode* cur= q1.front();
                q1.pop();
                vec.push_back(cur->val);
                if (cur->left) q2.push(cur->left);
                if (cur->right) q2.push(cur->right);
            }
            res.insert(res.begin(),vec);     //if we want the opposite order, use push_back
            if (q2.empty()) break;
            else {
                q1.swap(q2);
                queue<TreeNode*> emptyq;
                q2.swap(emptyq);
            }
        }
    }

7 Same Tree

    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        
        if (p->val!=q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        

    }

8 Lowest common ancestor of Binary Search Tree

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {        
        if (!root|| !p ||!q) return root;
        if (p ==root || q==root) return root;
        
        if (p->val<root->val){        
            if ( q->val < root->val) return lowestCommonAncestor(root->left, p, q);
            else return root;
        } else {
            if (q->val < root->val) return root;
            else  return lowestCommonAncestor(root->right, p, q);
        }        
    }

if it is a binary tree (not sorted BST), the problem is harder.

One solution:
1) Build a path of finding a node;
2) Compare the latest common node in two paths.

Path builder code:

    bool findNode(TreeNode* root, TreeNode*p, vector<TreeNode*>&path){
        if (!root || !p) return false;        
        path.push_back(root);
        if (root == p) return path;
        
        vector<TreeNode*> pathL, pathR;
        if (findNode(root->left, p, pathL)) {
            path.insert(path.end(), pathL.begin(), pathL.end());
            return true;
        } else if (findNode(root->right, p, pathR)){
            path.insert(path.end(), pathR.begin(), pathR.end());
            return true;
        } else return false;        
    }

LCA code:
   TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {        
        vector<TreeNode*> pathP, pathQ;
        
        findNode(root, p, pathP);
        findNode(root, q, pathQ);
        int L=min(pathP.size(),pathQ.size());
        if (L<=1) return root;
         for (int i=1; i<L; ++i)
               if (pathP[i]!=pathQ[i]) return pathP[i-1];                
         return pathP[L-1];
    }

9. isBalancedTree

Simply check depth differences recursively.

    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        if (abs(hTree(root->left)-hTree(root->right))>1) return false;
        return isBalanced(root->left) && isBalanced(root->right);
    }

10 is Symmetric

This is a level order traversal.  Then for each layer check if they are symmetric.  I used stack, but queue is more natural.

One tricky part:  The nullptr need to push in each layer for checking structure symmetric.  There are cases that all the values are symmetric but structure is not.

    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        if (!root->left && !root->right ) return true;
        stack <TreeNode*> s;
        s.push(root);
        bool root_layer=true;
        vector<TreeNode*> oneLayer;
 //breadth first extension;
        while (!s.empty()){
            oneLayer.push_back(s.top()); s.pop();            
            if (s.empty()){
                //check oneLayer toplopical and value;
                if (!root_layer ){
                    if (oneLayer.size()%2!=0) return false;
                    for (int i=0; i<oneLayer.size()/2; ++i){
 //both nullptr;
                        if ((oneLayer[i]==nullptr) && (oneLayer[oneLayer.size()-1-i]==nullptr) ) continue; 
//only one nullptr
                        if ((oneLayer[i]==nullptr) || (oneLayer[oneLayer.size()-1-i]==nullptr) ) return false; 
//neither nullptr, but diff val 
                        if (oneLayer[i]->val!= oneLayer[oneLayer.size()-1-i]->val) return false;     
                    }
                }                    //still alive, prepare next layer
                
                for (TreeNode* node: oneLayer){
                    if (node){
                        s.push(node->left);
                        s.push(node->right);
                    }
                 } 
                oneLayer.clear();
                root_layer=false;
            }
        }
        return true;
    }