対称ツリー( JavaScriptを使用した)

6264 ワード

今日、対称ツリーアルゴリズム問題の解決法を示します.
これが問題です

この問題では、バイナリツリーがその構造と値に対称かどうかをテストする必要があります.問題は、2つの木が互いの反射を反射するときですか?
左の部分木が右の部分木の鏡反射であるならば、木は対称です.私たちが木の真ん中に線を引くならば、木はそれ自体で折ることができます、そして、そのノード値は等価です.
今、私は再帰的にそれを解決するつもりです.
1)まず、ルートノードをチェックします.NULLの場合、それ以上のアクションは必要ない.NULLでない場合は、再帰的に進み、左右の部分木をチェックする必要があります.
var isSymmetric = function(root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
};
2)左のサブツリーと右のサブツリーが両方ともNULLであれば、それらは対称であることを意味する.それらのうちの1つがNULLであるならば、それらは非対称です.
var isSymmetric = function(root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
};

const isMirror = function(leftSub, rightSub) {
    if (leftSub == null && rightSub == null) return true;
    if (leftSub == null || rightSub == null) return false;
}
3 )もし両方ともNULLでなければ、値をチェックする必要があります.それらが同じであるならば、我々は左と右のノードへの再帰を続けるつもりです.左のサブツリーの左のノードが我々の右のサブツリーの右のノードに等しいことを確認しなければなりません、そして、我々の左の下位木の右のノードは我々の右のサブツリーの左側のノードと同等です.
var isSymmetric = function(root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
};

const isMirror = function(leftSub, rightSub) {
    if (leftSub == null && rightSub == null) return true;
    if (leftSub == null || rightSub == null) return false;

    return (leftSub.val === rightSub.val 
            && isMirror(leftSub.left, rightSub.right) 
            && isMirror(leftSub.right, rightSub.left))
}