剣指offer-二叉探索木のk番目の接点-java
1272 ワード
タイトルの説明:
二叉探索ツリーを指定し、k番目の大きなノードを見つけてください.たとえば、5/3 7///2 4 6 8の3番目のノードの値は、ノードの数値の大きさ順に4になります.
構想解析:二叉木の中序遍歴、小から大出力ノード までは、ノードをスタックで格納し、カウントする. サイクル条件:ノードが空ではなく、スタックが空ではない ノードは空ではなくスタックに入り、そうでなければスタックを出て、k番目のノードまで遍歴すると ループから飛び出します.
コード:
二叉探索ツリーを指定し、k番目の大きなノードを見つけてください.たとえば、5/3 7///2 4 6 8の3番目のノードの値は、ノードの数値の大きさ順に4になります.
構想解析:
コード:
import java.util.Stack;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode KthNode(TreeNode pRoot, int k)
{
if(pRoot == null||k<=0)
return null;
int index = 0;
TreeNode kthNode = null;
TreeNode node = pRoot;
Stack stack = new Stack();
while(node!=null||!stack.isEmpty()){
if(node!=null){
stack.push(node);
node = node.left;
}else{
node = stack.pop();
index++;
if(index==k){
kthNode = node;
break;
}
node = node.right;
}
}
return kthNode;
}
}