JZ62---서열화 두 갈래 나무

7961 단어 검지offer
제목 설명: 두 갈래 검색 트리를 정하고 그 중의 k번째 작은 결점을 찾으세요.예를 들어 (5, 3, 7, 2, 4, 6, 8)에서 결점 수치의 크기에 따라 세 번째 작은 결점의 값은 4이다.
문제: 두 갈래 나무의 특성에 따라 두 갈래 나무를 샅샅이 뒤지면서 얻은 서열이 질서정연하다는 것을 알 수 있다.이 특성을 이용하여 이 문제를 해결할 수 있다.
해법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;
    }

좋은 웹페이지 즐겨찾기