Traverse binary tree by level

두 갈래 나무는 차원에 따라 두루 다니는데, 매우 간단하고, 대열하면 된다.두 갈래 나무가 가득하다고 가정하면 공간의 복잡도는 얼마나 됩니까?마지막 대기열은 N/2 개의 잎 노드를 포함하기 때문에 O(n)여야 합니다.
만약 O(lgn) 공간을 요구하면 어떻게 실현합니까?렉 걸렸어...
원래 귀속적인 방식으로 O(lgn)의 차원별 반복을 실현할 수 있었는데 이때 창고 공간을 사용했다.
void printLevel(TreeNode *root, int level) {
	if (root == NULL || level < 1) {
		return;
	}

	if (level == 1) {
		cout << root->val << " ";
		return;
	}

	printLevel(root->left, level - 1);
	printLevel(root->right, level - 1);
}

int getDepth(TreeNode *root) {
	if (root == NULL) {
		return 0;
	}

	int ldepth = getDepth(root->left);
	int rdepth = getDepth(root->right);
	return (max(ldepth, rdepth) + 1);
}

int _tmain(int argc, _TCHAR* argv[])
{
	TreeNode *root = new TreeNode(1);
	root->left = new TreeNode(2);
	root->left->left = new TreeNode(3);
	root->left->right = new TreeNode(5);
	root->right = new TreeNode(4);
	root->right->right = new TreeNode(6);
	root->right->right->left = new TreeNode(7);
	root->right->right->left->right = new TreeNode(9);
	root->right->right->right = new TreeNode(8);

	int levels = getDepth(root);
	for (int i = 1; i <= levels; ++i) {
		printLevel(root, i);
		cout << endl;
	}

	return 0;
}

예는 두 갈래 나무가 아니라 이전에 프로그램에서 만든 나무입니다.기본 사상이 도착했어. - 약간 tricky야, 생각하기 힘들어.

좋은 웹페이지 즐겨찾기