二叉樹の面接問題のまとめ(一)
14440 ワード
title:二叉樹面接試験問題まとめ(一)categories:データ構造date:2016-08-18
著作権声明:当駅は開放的な「知識共有署名-非商業的使用-同じ方法で許諾協議」を採用して許可します.
すべての文章のコードは、私のgithubに表示されます.名前はクラス全体の名前によって探すことができます.
二叉樹のまとめ点数を計算します.
ツリーの定義:
考え方:は、伝えられたルートノードが空かどうかを判断し、空ならそのまま0 に戻る.左サブツリー+右サブツリーの総数にルートノードを加えると、このツリーの総括点数 です.では、左サブノードの総数と右サブノードの総数は、どうやって再帰的な方式で求められますか? 毎回、再帰されるノードの左ノードの総数＋右ノードの総数＋1、そのうちの1は、現在のルートノードを指し、このように毎回再帰的に得られる結果は、現在のノードの中性子ノードの総数＋現在のノード である.
コードの実装:
テストコード:
ループ
考え方:は、ノードをある「コンテナ」に格納することによって実現され、ここでは、格納するノードがすぐに使用できることを考慮して、キュー を考慮する.は、ルートノードが空であるかどうかを判断し、0に戻る.そうでないと に保存されます.は、ノードの総数 を記録する変数countを定義する.次に、列が空いているかどうかを循環判断します. が空でなければ、まずチームの先頭のノードを得て、つまり先頭ノードを列から出します. は、ヘッダノードの左ノードが空であるかどうかを判断し、count＋1ではなく、左ノードをキュー に参加する.は、ヘッドノードの右ノードが空であるかどうかを判断し、count＋1ではなく、右ノードをキュー に追加する.最後にcount に戻ります.
コードの実装:
二叉樹の深さを計算します.
再帰する
考え方:は、左右のサブノードの深さをそれぞれ取得し、大きな値＋1を取ることが、この二叉樹の深さ である.では、各ノードは、左右のサブノード を有していてもよい.
コードの実装:
テストコード:
反復
考え方:は、ルートノードが空かどうか判断する .は、3つの変数を定義し、それぞれ階数、現在の層のノード数、次の層のノード数 である.キューが空でない場合、現在のノードを得て、現在の節分点数−1を決定し、現在のノードが左右のノードがあるかどうかを判断し、ある場合はキューに入れ、次の層のノード数 を修正する.は、前の層のノード数が0の場合、深さ＋1を、現在の層を次の層 に移動する.
【全文完了】
著作権声明:当駅は開放的な「知識共有署名-非商業的使用-同じ方法で許諾協議」を採用して許可します.
すべての文章のコードは、私のgithubに表示されます.名前はクラス全体の名前によって探すことができます.
二叉樹のまとめ点数を計算します.
ツリーの定義:
public class BinaryTree {
int value;
BinaryTree leftChild;
BinaryTree rightChild;
public BinaryTree(int value) {
super();
this.value = value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public BinaryTree getLeftChild() {
return leftChild;
}
public void setLeftChild(BinaryTree leftChild) {
this.leftChild = leftChild;
}
public BinaryTree getRightChild() {
return rightChild;
}
public void setRightChild(BinaryTree rightChild) {
this.rightChild = rightChild;
}
}
考え方:
コードの実装:
public class CountNodes {
/**
*
*
* @param root
* @return
*/
public static int getCount(BinaryTree root) {
//
if (root == null) {
// 0
return 0;
} else {
// ，
// +
return getCount(root.getLeftChild())
+ getCount(root.getRightChild()) + 1;
}
}
テストコード:
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
System.out.println(CountNodes.getCount(n1));
}
}
ループ
考え方:
コードの実装:
public static int getCountByIteration(BinaryTree root) {
int count = 1;
if (root == null) {
return 0;
}
// ， root
Queue binaryTrees = new LinkedList();
binaryTrees.add(root);
//
while (!binaryTrees.isEmpty()) {
//
BinaryTree currentNode = binaryTrees.remove();
// ， ， count
if (currentNode.getLeftChild() != null) {
count++;
binaryTrees.add(currentNode.getLeftChild());
}
if (currentNode.getRightChild() != null) {
count++;
binaryTrees.add(currentNode.getRightChild());
}
}
//
return count;
}
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
System.out.println(CountNodes.getCountByIteration(n1));
}
}
二叉樹の深さを計算します.
再帰する
考え方:
コードの実装:
public static int countDeepness(BinaryTree root) {
//
// 0
if (root == null)
return 0;
int left = countDeepness(root.getLeftChild());
int right = countDeepness(root.getRightChild());
// +1，1
return Math.max(left, right) + 1;
}
テストコード:
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
System.out.println(CountTheDeepness.countDeepness(n1));
}
}
反復
考え方:
public static int countDeepnessByIteration(BinaryTree root) {
//
if (root == null)
// 0
return 0;
// ， ， ，
int depth = 0, currentLevelNodes = 1, nextLevelNodes = 0;
//
Queue binaryTrees = new LinkedList();
binaryTrees.add(root);
//
while (!binaryTrees.isEmpty()) {
//
BinaryTree currentNode = binaryTrees.remove();
// -1
currentLevelNodes--;
//
if (currentNode.getLeftChild() != null) {
// ，
binaryTrees.add(currentNode.getLeftChild());
nextLevelNodes++;
}
if (currentNode.getRightChild() != null) {
binaryTrees.add(currentNode.getRightChild());
nextLevelNodes++;
}
// 0
if (currentLevelNodes == 0) {
// +1
depth++;
//
currentLevelNodes = nextLevelNodes;
nextLevelNodes = 0;
}
}
return depth;
}
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
System.out.println("iteration:"+CountTheDeepness.countDeepnessByIteration(n1));
}
}
【全文完了】