JZ62---서열화 두 갈래 나무
7961 단어 검지offer
문제: 두 갈래 나무의 특성에 따라 두 갈래 나무를 샅샅이 뒤지면서 얻은 서열이 질서정연하다는 것을 알 수 있다.이 특성을 이용하여 이 문제를 해결할 수 있다.
해법1: 귀속
public class Solution {
TreeNode kNode = null;
int count = 0;
private void help(TreeNode root, int k) {
if(root == null){
return;
}
help (root.left,k);
count++;
if(count == k){
kNode = root;
return;
}
if(count > k){
return;
}else{
help (root.right,k);
}
}
TreeNode KthNode(TreeNode pRoot, int k) {
if(pRoot == null || k <= 0){
return null;
}
help(pRoot,k);
return kNode;
}
}
해법2: 비귀속, 창고 이용.
TreeNode KthNode(TreeNode pRoot, int k)
{
if(pRoot == null || k <= 0){
return null;
}
Stack<TreeNode> stack = new Stack<>(); //
TreeNode cur = pRoot;
//while
while(!stack.isEmpty() || cur != null){
if(cur != null){
stack.push(cur); // null,
cur = cur.left;
}else{
null , 。
cur = stack.pop();
if(--k == 0){ //
return cur;
}
cur = cur.right;
}
}
return null;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
20200326 - 검지offer 면접문제 27: 두 갈래 나무의 거울이솔 위 안에 28문제의 답안이 있는데 어떻게 꼬치는지 모르겠다.간단해....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.