N 노드의 이진 트리를 재귀 적으로 탐색하면 실행 스택에서 N 공간을 차지합니다. iteration을 사용하면 명시 적 스택에서 N 개의 공백을 사용해야합니다.
질문은 재귀 순회가 반복적 순회가 사용하는 O(N)것처럼 공간 복잡성을 사용한다고 말하는 것 입니까? 메모리 제한으로 인해 나를 제한하는 일부 플랫폼에서 순회 코드를 실행하는 것과 관련하여 이야기하고 있습니다. 또한 나는 반복을 직접 구현하는 것에 대해 이야기하고 있지 않습니다 (접근법 중 하나가 괜찮다고 말할 수 있음) KthSmallestElement().BST를 통해 일종의 순회를 사용하는 BST에서 알고리즘을 구현 하고 있습니다.
내 코드가 공간 제한에서 실패하지 않도록 공간 복잡성 측면에서 반복적 접근 방식 또는 재귀 적 접근 방식을 사용해야합니까?
명확하게 말하면 :
다음은 내가 구현 한 것입니다.
int Solution::kthsmallest(TreeNode* root, int k) {
stack<TreeNode *> S;
while(1)
{
while(root)
{
S.push(root);
root=root->left;
}
root=S.top();
S.pop();
k--;
if(k==0)
return root->val;
root=root->right;
}
}
내 친구가 구현 한 내용은 다음과 같습니다.
class Solution {
public:
int find(TreeNode* root, int &k) {
if (!root) return -1;
// We do an inorder traversal here.
int k1 = find(root->left, k);
if (k == 0) return k1; // left subtree has k or more elements.
k--;
if (k == 0) return root->val; // root is the kth element.
return find(root->right, k); // answer lies in the right node.
}
int kthsmallest(TreeNode* root, int k) {
return find(root, k); // Call another function to pass k by reference.
}
};
그래서 둘 중 어느 것이 더 낫고 어떻게?
메모리 사용에 관심이 있다면 트리가 균형을 이루도록해야합니다 . 즉, 깊이가 노드 수보다 작은 지 확인해야합니다 . N 노드가있는 완벽하게 균형 잡힌 이진 트리는 깊이 log 2 N (반올림)을 갖 습니다.
바이너리 트리의 모든 노드를 방문하는 데 필요한 메모리는 잘못 생각하는 노드 수가 아니라 트리의 깊이에 비례하기 때문에 중요합니다. 재귀 또는 반복 프로그램은 이전에 방문한 다른 노드가 아니라 루트에서 현재 노드까지의 경로를 "기억"해야합니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다