対称ツリー( JavaScriptを使用した)
6264 ワード
今日、対称ツリーアルゴリズム問題の解決法を示します.
これが問題です
この問題では、バイナリツリーがその構造と値に対称かどうかをテストする必要があります.問題は、2つの木が互いの反射を反射するときですか?
左の部分木が右の部分木の鏡反射であるならば、木は対称です.私たちが木の真ん中に線を引くならば、木はそれ自体で折ることができます、そして、そのノード値は等価です.
今、私は再帰的にそれを解決するつもりです.
1)まず、ルートノードをチェックします.NULLの場合、それ以上のアクションは必要ない.NULLでない場合は、再帰的に進み、左右の部分木をチェックする必要があります.
これが問題です
この問題では、バイナリツリーがその構造と値に対称かどうかをテストする必要があります.問題は、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))
}
Reference
この問題について(対称ツリー( JavaScriptを使用した)), 我々は、より多くの情報をここで見つけました https://dev.to/urfan/leetcode-symmetric-tree-with-javascript-3404テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol