검지offer - 두 갈래 검색 트리의 두 번째 노드

1322 단어 검지offer

제목 설명


두 갈래 수색 나무를 정해 주십시오. 그중의 k번째 작은 결점을 찾아 주십시오.예를 들어 (5, 3, 7, 2, 4, 6, 8)에서 결점 수치의 크기에 따라 세 번째 작은 결점의 값은 4이다.

생각


귀속적인 방식으로 뿌리 노드에 깊이 들어간 왼쪽 아이가 빈 노드에 닿을 때까지 계속 귀속한 다음에 현재 노드를 거슬러 올라간다.다시 같은 방식으로 오른쪽 아이들을 두루 돌아다닌다.이 기간 동안 매 노드를 방문할 때마다 우리는 k를 줄이고 k가 0이 될 때까지 이 노드가 바로 k의 노드라는 것을 설명한다.
class Solution {
public:
    int m;
    TreeNode* ans;
    void dfs(TreeNode* p){
        if(!p || m < 1) return;// NULL/ :
        dfs(p -> left);// , , 
        if(m == 1) ans = p;//  / m- 1 , m 
        if(--m > 0) dfs(p -> right);//  /  ( )
    }
    TreeNode* KthNode(TreeNode* p, unsigned int k){
        ans = NULL; m = k;//  ans=NULL  NULL
        dfs(p);
        return ans;
    }
};
, , , , , , , k 。
class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot,unsigned int k)
    {
        if(!pRoot) return nullptr;
        stack res;
        TreeNode* p =pRoot;
        while(!res.empty() || p ){//res  and  
            while(p){
                res.push(p);
                p = p->left;
            }
            TreeNode* node = res.top();
            res.pop();
            if((--k)==0) return node;
            p = node->right;
        }
        return nullptr;
    }
};

좋은 웹페이지 즐겨찾기