二分木に関連するアルゴリズム

、木がバランスの取れた二分木かどうかを判断する方法

崩壊のアイデア

トップダウンは、最初にツリーの高さの現在のノードを見つけるために関数を設定するどのくらい、その後、バランスの要因は、左と右のサブツリー間の高さの差です。本質はまだ木の再帰的走査の使用です。

コードの実装

 function isBalacne(root) {
 if (!root) {
 return true;
 }
 // 左右の部分木が釣り合った木かどうかを再帰的に判定する。
 return Math.abs(getHeight(root.left), getHeight(root.right)) <= 1 && isBalacne(root.left) && isBalacne(root.right);
 }
 function getHeight(node) {
 if (!node) {
 return 0;
 }
 return 1 + Math.max(getHeight(node.left), getHeight(node.right));
 }

バイナリツリーの最大深さを計算するアルゴリズムを設計します。

崩壊のアイデア

• 終了条件を見つける：ノードが空のとき
• ノードが空ではない場合、左と右のサブツリーの高さは、現在のノードの高さを示すために1を追加しながら、最大値を求めていたので、0を返します。
• 時間の複雑さ：O(n)
• 時間の複雑さ O(n)

コードの実装

 function maxDepth(root) {
 if (!root) {
 return 0;
 }
 // 左部分木の深さを再帰的に計算する。
 const left = maxDepth(root.left);
 // 右部分木の深さを再帰的に計算する。
 const right = maxDepth(root.right);
 // ここで1を加えるのは
 return Math.max(left, right) + 1;
 }

、2つの2進木が同じかどうかを判断するために戻るアルゴリズムを設計します。

崩壊のアイデア

• 終了条件と戻り値：両方のツリーのカレント・ノードがnullのときtrueを返す 片方がnullでもう片方がnullでないときfalseを返す 両方がnullでなく値が等しくないときfalseを返す
• 実行処理：終了条件が満たされたら戻り、満たされなかった場合は左右の部分木が同じかどうかを判断し、コード内の短絡効果に注意する必要があります。
• 時間の複雑さ：O(n)

 function isSameTree(tree1, tree2) {
 // 両方の木のノードは空である
 if (!tree1 && !tree2) {
 return true;
 }
 // 木のノードが1つだけ空である
 if (!tree1 || !tree2) {
 return false;
 }
 // 2つの木のノードの値は同じではない
 if (tree1.val != tree2.val) {
 return false;
 }
 // つの木のすべてのノードを再帰的に判定する。
 return isSameTree(tree1.left, tree2.left) && isSameTree(tree1.right, tree2.right);
 }