再帰ツリー対称

Question

私は、バイナリツリーが対称であるか否かを決定するために、次のコードスニペットを書かれている：

/** 
* Definition for a binary tree node. 
* struct TreeNode { 
*  int val; 
*  TreeNode *left; 
*  TreeNode *right; 
*  TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
* }; 
*/ 
class Solution { 
public: 
    bool symmetricityChecker(TreeNode* root, int level) { 
     bool isValid=false; 

     if(root==NULL) 
      return true; 

     if(level==1) 
      isValid = root->left->val==root->right->val; 

     if(root->left!=NULL && root->right!=NULL) { 
      if(root->left->left!=NULL && root->right->right!=NULL) 
       isValid = root->left->left->val==root->right->right->val; 

      if(root->left->right!=NULL && root->right->left!=NULL) 
       isValid = root->left->right->val==root->right->left->val; 
     } 

     return isValid && symmetricityChecker(root->left, level+1) && symmetricityChecker(root->right, level+1); 
    } 

    bool isSymmetric(TreeNode* root) { 
     return symmetricityChecker(root, 0); 
    } 
}; 

私の目的は、根の左と右の子供が同じであれば、私はチェックし、レベル1であり、 （このレベルではルートとその2人の子供が存在するため）。残りのすべてのレベルについて、rootの子leftの子のleft子が、の子のrightの子の子であるかどうかを確認します。right同様に、私はrootの子のrightの子がleftの子の子がrootのrightの子のleftと等しいかどうかをチェックします。 （これはそうである。なぜなら、ルートの即時の左右の子の対称性は、以前の再帰呼び出しですでにチェックされているからである）。

私のアルゴリズムは正しいと思われますが、誤った結果が出ています。私のロジックが間違っている場合、または実装にエラーがある場合、誰かが親切に指摘できますか？

編集：私は入力[1,2,2,3,4,4,3]のコードをテストしました。私は答えがtrueであると予想しますが、代わりにfalseを得ます。したがって、論理の脆弱性が私のアプローチにあるかどうかはわかりません。あなたはそれをやっているところ

Answer 1

間違った部分がある：

return isValid && symmetricityChecker(root->left, level+1) && symmetricityChecker(root->right, level+1); 

単一の子ノードにsymmetricityCheckerを呼び出すことによって、あなたは子供が同様に対称であることを期待しているが、これは真実ではありません。したがって、サブツリー[2,3,4]は対称ではなく、これが真でないとしてもツリー全体が対称ではないと考えるので、失敗します。

対称性を再帰的にチェックするには、1つではなく、2つのノード（左と右）を状態として保持する必要があります。 2つのノードが対称であることを確認したら、入れ子のif条件で上でやっていることと同様のチェックで子ノードを再帰的にチェックします。

もう1つのアプローチは、BFSを作成し、同じレベルのすべてのノードが対称であることを確認することです。この方法では、同じ配列のすべてのノードが隣り合っているため、配列が対称であるかどうかをチェックするのと同じくらい簡単に行う必要があります。

EDIT：ルートの子供たちと一緒に、このメソッドを呼び出して、あなただけのルートを持っている冒頭で

bool symmetricityChecker(left, right) { 
    // Write the base case, check for nulls, corner cases, etc. 
    if(left != right) return false 
    return symmetricityChecker(left.left, right.right) && 
      symmetricityChecker(left.right, right.left) 
} 

： は擬似コードを追加します。