LeetCode 919 완전 이 진 트 리 삽입 기 complete binary tree inserter

완전 이 진 트 리 는 각 층 (마지막 층 을 제외 하고) 이 완전히 채 워 져 있 고 모든 결점 은 가능 한 한 왼쪽 에 집중 되 어 있다.
완전 이 진 트 리 로 초기 화 된 데이터 구 조 를 설계 합 니 다. CBTInserter 는 다음 과 같은 몇 가지 조작 을 지원 합 니 다.

CBTInserter(TreeNode root)        root             ；
CBTInserter.insert(int v)   TreeNode         node.val = v                  ，       TreeNode       ；
CBTInserter.get_root()         。

예시 1:
입력: input = ["CBTInserter", "insert", "get root"], input = [[[1], [2], []] 출력: [null, 1, [1, 2]]]
예시 2:
입력: input = ["CBTInserter", "insert", "insert", "get root"], input = [[1, 2, 3, 4, 5, 6], [7], [8], [] 출력: [null, 3, 4, [1, 2, 3, 4, 5, 6, 7, 8]]]
알림:

            ，    1   1000    。
           CBTInserter.insert     10000  。
                0   5000   。

제목 은 매우 간단 하 다. 나 무 는 스스로 만 들 필요 가 없다. 그 는 이미 만 들 었 고 완전히 이 진 트 리 라 는 것 을 보증한다.주로 삽입 작업 을 실현 하 는 것 이다.사실은 매우 간단 합 니 다. 이 진 트 리 노드 의 개 수 를 알 면 현재 노드 의 레이 블 은 원래 노드 의 개수 + 1 입 니 다. 이 레이 블 의 바 이 너 리 코드 만 보면 매번 left 를 선택해 야 하 는 지 right 를 선택해 서 이 위 치 를 찾 을 수 있 습 니 다.삽입 완료 후 노드 개 수 를 업데이트 하면 됩 니 다.

class CBTInserter{
private:
	TreeNode* m_root;
	int m_num;
	int count_node_num(TreeNode* root)
	{
		if(root==NULL)
			return 0;
		int left_num=count_node_num(root->left);
		int right_num=count_node_num(root->right);
		return left_num+right_num+1;
	}
public:
    CBTInserter(TreeNode* root)
	{
		this->m_root=root;
		this->m_num=count_node_num(root);
    }
    int insert(int v)
	{
		int idx=m_num+1;
		TreeNode* root=m_root;
		vector binary_idx;
		while(idx)
		{
			binary_idx.push_back(idx%2);
			idx=idx/2;
		}
		reverse(binary_idx.begin(),binary_idx.end());
		for(int i=1;ileft;
			else
				root=root->right;
		}
		if(!binary_idx[binary_idx.size()-1])
			root->left=new TreeNode(v);
		else
			root->right=new TreeNode(v);
		this->m_num=this->m_num+1;
		return root->val;
    }
    TreeNode* get_root()
	{
		return this->m_root;
    }
};

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

제1 6 장 파일 에서 텍스트 검색 도구: grep 명령 과 egrep 명령

제1 6 장 파일 에서 텍스트 검색 도구: grep 명령 과 egrep 명령 옵션 grep 명령 파일 에서 단 어 를 검색 하면 명령 은 "match pattern"을 포함 하 는 텍스트 줄 을 되 돌려 줍 니 다....

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

LeetCode 919 완전 이 진 트 리 삽입 기 complete binary tree inserter

좋은 웹페이지 즐겨찾기