二叉樹-よくある簡単なアルゴリズムの問題

篇一:二叉樹-最終版を遍歴します.二叉樹-創建、再構成、転化編三:二叉樹-詳細解二叉並べ替え木編四:二叉樹-詳細解バランス二叉樹AVL篇五:二叉樹-一般的な簡単なアルゴリズム問題
二叉の木の高さを求めます

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

二叉の木の最小の深さを求めます.
上に最大の深さ(つまり二叉の高さ)を求めてみます.下に最小の深さを求めます.

int minDepth(TreeNode* root) 
{
    if (root == NULL) return 0;
    if (root->left == NULL) 
       return minDepth(root->right) + 1;
    else if (root->right == NULL) 
       return minDepth(root->left) + 1;
    else 
       return min(minDepth(root->left), minDepth(root->right)) + 1;
}

二叉樹の高さのバランスを判断します.

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

二つの二叉の木が等しいかどうかを判断します.

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

二叉の木は対称の木かどうかを判断します.

  bool Symmetry(TreeNode* left, TreeNode* right)
  {
      if(!left && !right) return true;
      if(!left || !right) return false;
      if(left->val != right->val) return false;
      return  Symmetry(left->left, right->right) && Symmetry(left->right, right->left);  
  }
  bool isSymmetric(TreeNode* root)
  {
       if(root==NULL) return true;
       else
           return Symmetry(root->left,root->right); 
       return false;        
  }

フォークを反転
再帰版:

TreeNode *invertTree(TreeNode *root) 
{
     if (root == NULL) return NULL;
     TreeNode *tempRight = root->right;
     root->right = invertTree(root->left);
     root->left = invertTree(tempRight);
     return root;
}

上で交換しないでください.std:swapで直接実現できます.

TreeNode* invertTree(TreeNode* root) {
    if (root==NULL) return NULL;
    invertTree(root->left);
    invertTree(root->right);
    std::swap(root->left, root->right);
    return root;
}

再帰版ではない:

 TreeNode* invertTree(TreeNode* root) 
 {
     if(!root) return NULL;
     queue  myqueue;
     myqueue.push(root);
     while(myqueue.size()>0)
     {
         TreeNode* pnode=myqueue.front();
         myqueue.pop();
         if(pnode)
         {
             myqueue.push(pnode->left);
             myqueue.push(pnode->right);

             TreeNode* pleft=pnode->left;
             pnode->left=pnode->right;
             pnode->right=pleft;
         }
     }
     return root;
 }

これはもちろんstdを使ってもいいです.swap、コードは以下の通りです.

 TreeNode* invertTree(TreeNode* root) 
 {
     if(!root) return NULL;
     queue  myqueue;
     myqueue.push(root);
     while(myqueue.size()>0)
     {
         TreeNode* pnode=myqueue.front();
         myqueue.pop();
         if(pnode)
         {
             myqueue.push(pnode->left);
             myqueue.push(pnode->right);           
             std::swap(pnode->left,pnode->right);
         }
     }
     return root;
 }