征戦二叉樹-第二駅
7898 ワード
前回の二叉木に続いて、今回は難易度が深まりました.前序、後序、中序遍歴の反復アルゴリズムを練習しました.他にもいくつかのアルゴリズムがあります.じゃ、早く見てみましょう.
1.順方向ループ(反復)
2.中間パス(反復)
3.後段遍歴(反復)
考え方:ルートノードは左の子供と右の子供が訪問してからアクセスできることを保証するため、いずれかのノードPについては、まずスタックに入れます.Pに左の子と右の子が存在しない場合は、直接アクセスできます.あるいはPには左または右の子が存在するが,左および右の子が既に訪問されている場合,同様にノードに直接アクセスすることができる.上記の2つ以外の場合、Pの右の子と左の子を順番にスタックに入れることで、スタックトップ要素を取るたびに、左の子が右の子の前に訪問され、左の子と右の子が根結>点の前に訪問されることを保証します.
4.2つのツリーがミラーリングされているかどうかを判断する
5.ミラーツリー、またはツリーの反転を求める
6.接続ノードの最小祖先ノードを探す
7.ツリーの2つのノード間の最大距離を取得する
考え方:ツリー内の2つのノードの最長距離には3つの状況がある可能性があります.
1.左サブツリーの最大深さ+右サブツリーの最大深さは二叉木の最長距離
2.左サブツリーの最長距離は二叉木の最長距離である
3.右子樹種の最長距離は二叉樹の最長距離である
8.ツリーと整数を入力し、ツリー内のノード値の合計と入力整数のすべてのパスを印刷します.
注意:ここでのパスは、ルートノードからリーフノードまでです.
まとめ
以上は今回练习した二叉木のいくつかのアルゴリズムの问题で、もちろん、他にも実现の方法があります.例えば、后序遍歴の反復アルゴリズムには他の考え方があります.ここで私は理解しやすいと思います.参考にしてください.もしあなたが比较的良い考え方と他の书き方があれば、分かち合うことができます.
次の練習は、二叉木の木探しの練習を始めますので、お楽しみに!
リファレンス
1つの文章は面接中の二叉木のテーマを完成します(java実現)
1.順方向ループ(反復)
/**
*
* ：
* @param root
* @return
*/
public List preOrderWithIteration(TreeNode root){
if (root == null) {
return null;
}
List list = new ArrayList();
Stack> stack = new Stack>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode currentNode = stack.pop();
list.add(currentNode.getData());
if (currentNode.right != null) {
stack.push(currentNode.right);
}
if (currentNode.left != null) {
stack.push(currentNode.left);
}
}
return list;
}
2.中間パス(反復)
/**
*
* @param root
* @return
*/
public List inOrderWithIteration(TreeNode root){
if(root == null){
return null;
}
List list = new ArrayList();
Stack> stack = new Stack>();
while(root != null || !stack.isEmpty()){
while(root != null){
stack.push(root);
root = root.left;
}
if (!stack.isEmpty()) {
TreeNode currentNode = stack.pop();
list.add(currentNode.getData());
root = currentNode.right;
}
}
return list;
}
3.後段遍歴(反復)
考え方:ルートノードは左の子供と右の子供が訪問してからアクセスできることを保証するため、いずれかのノードPについては、まずスタックに入れます.Pに左の子と右の子が存在しない場合は、直接アクセスできます.あるいはPには左または右の子が存在するが,左および右の子が既に訪問されている場合,同様にノードに直接アクセスすることができる.上記の2つ以外の場合、Pの右の子と左の子を順番にスタックに入れることで、スタックトップ要素を取るたびに、左の子が右の子の前に訪問され、左の子と右の子が根結>点の前に訪問されることを保証します.
/**
* ，
* @param root
* @return
*/
public List postOrderWithIteration(TreeNode root){
if(root == null){
return null;
}
List list = new ArrayList();
Stack> stack = new Stack>();
TreeNode curNode;
TreeNode preNode = null;
stack.push(root);
while(!stack.isEmpty()){
curNode = stack.peek();
if ((curNode.left == null && curNode.right == null) || (preNode != null
&& (preNode == curNode.left || preNode == curNode.right))) {
list.add(curNode.getData());
preNode = curNode;
stack.pop();
}
else {
if (curNode.right != null) {
stack.push(curNode.right);
}
if(curNode.left != null){
stack.push(curNode.left);
}
}
}
return list;
}
4.2つのツリーがミラーリングされているかどうかを判断する
/**
*
* @param root1
* @param root2
* @return
*/
public boolean isMirror(TreeNode root1,TreeNode root2){
if (root1 == null && root2 == null) {
return true;
}
else if (root1 != null || root2 != null) {
return false;
}
else if(root1.getData() != root2.getData()){
return false;
}
return isMirror(root1.left, root2.right) && isMirror(root1.right, root2.left);
}
5.ミラーツリー、またはツリーの反転を求める
/**
* ，
* @param root
* @return
*/
public TreeNode mirrorTreeNode(TreeNode root){
if (root == null) {
return null;
}
TreeNode left = mirrorTreeNode(root.left);
TreeNode right = mirrorTreeNode(root.right);
root.left = right;
root.right = left;
return root;
}
6.接続ノードの最小祖先ノードを探す
/**
*
* @param root
* @param nodeA
* @param nodeB
* @return
*/
public TreeNode getLowestAncestor(TreeNode root,TreeNode nodeA,TreeNode nodeB){
if (findNode(root.left,nodeA)) {
if (findNode(root.right, nodeB)) {
return root;
}
else {
return getLowestAncestor(root.left, nodeA, nodeB);
}
}
else {
if (findNode(root.left, nodeB)) {
return root;
}
else {
return getLowestAncestor(root.right, nodeA, nodeB);
}
}
}
private boolean findNode(TreeNode root, TreeNode node) {
if (root == null || node == null) {
return false;
}
if (root == node) {
return true;
}
boolean isFound = findNode(root.left, node);
if (!isFound) {
isFound = findNode(root.right, node);
}
return isFound;
}
7.ツリーの2つのノード間の最大距離を取得する
考え方:ツリー内の2つのノードの最長距離には3つの状況がある可能性があります.
1.左サブツリーの最大深さ+右サブツリーの最大深さは二叉木の最長距離
2.左サブツリーの最長距離は二叉木の最長距離である
3.右子樹種の最長距離は二叉樹の最長距離である
/**
*
* @param root
* @return
*/
public int getMaxDistance(TreeNode root){
return getMaxDistanceHolder(root).maxDistance;
}
private DistanceHolder getMaxDistanceHolder(TreeNode root){
if (root == null) {
return new DistanceHolder(-1,0);
}
DistanceHolder leftHolder = getMaxDistanceHolder(root.left);
DistanceHolder rightHolder = getMaxDistanceHolder(root.right);
DistanceHolder result = new DistanceHolder();
result.maxDepth = Math.max(leftHolder.maxDepth, rightHolder.maxDepth) + 1;
result.maxDistance = Math.max(leftHolder.maxDepth + rightHolder.maxDepth,
Math.max(leftHolder.maxDistance, rightHolder.maxDistance));
return result;
}
/**
*
* @author Administrator
*
*/
private static class DistanceHolder{
public int maxDistance;
public int maxDepth;
public DistanceHolder(){}
public DistanceHolder(int maxDistance, int maxDepth) {
this.maxDistance = maxDistance;
this.maxDepth = maxDepth;
}
}
8.ツリーと整数を入力し、ツリー内のノード値の合計と入力整数のすべてのパスを印刷します.
注意:ここでのパスは、ルートノードからリーフノードまでです.
/**
*
* @param root
* @param k
* @return
*/
public List findAllPath(TreeNode root,int k){
List list = new ArrayList();
if (root == null) {
return list;
}
int sum = 0;
Stack> stack = new Stack>();
findAllPath(root, k,list,stack,sum);
return list;
}
private void findAllPath(TreeNode root, int k, List list,
Stack> stack, int sum) {
sum += root.getData();
stack.push(root);
if (root.left == null && root.right == null && sum == k) {
for(TreeNode node : stack){
list.add(node.getData());
}
}
if (root.left != null) {
findAllPath(root.left, k, list, stack, sum);
}
if (root.right != null) {
findAllPath(root.right, k, list, stack, sum);
}
stack.pop();// ， ，
}
まとめ
以上は今回练习した二叉木のいくつかのアルゴリズムの问题で、もちろん、他にも実现の方法があります.例えば、后序遍歴の反復アルゴリズムには他の考え方があります.ここで私は理解しやすいと思います.参考にしてください.もしあなたが比较的良い考え方と他の书き方があれば、分かち合うことができます.
次の練習は、二叉木の木探しの練習を始めますので、お楽しみに!
リファレンス
1つの文章は面接中の二叉木のテーマを完成します(java実現)