leetcode의 복구 바이너리 검색 트리
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(
n
) space is pretty straight forward. Could you devise a constant space solution?
confused what
"{1,#,2,3}" means? > read more on how binary tree is serialized on OJ. 사고방식: 두 갈래 나무의 중차가 두루 다니는데 만약에 어떤 노드의 전차 노드가 이 노드보다 크면 첫 번째 오류 위치에 대해 전차는 오류 위치이다.두 번째 오류 위치에 대해 말하자면 후속은 오류 위치이다. 제목은 공간을 신청하지 말라고 요구하기 때문에 귀속을 사용해야 한다. 다음에 우리는 귀속과 창고를 모두 실현한다.class Solution {
public:
void recoverTree(TreeNode *root) {
if(root == NULL)return;
TreeNode* pre = NULL,*n1 = NULL,*n2 = NULL;
findTwoNode(root,n1,n2,pre);
if(n1 && n2)
{
int temp = n1->val;
n1->val = n2->val;
n2->val = temp;
}
}
void findTwoNode(TreeNode* root,TreeNode* &n1,TreeNode* &n2,TreeNode* &pre)
{
if(root == NULL)return;
findTwoNode(root->left,n1,n2,pre);
if(pre && pre->val > root->val)
{
n2 = root;//
if(n1 == NULL)
{
n1 = pre;//
}
}
pre = root;
findTwoNode(root->right,n1,n2,pre);
}
};struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
void recoverTree(TreeNode *root) {
if(!root)return;
stack<TreeNode*> s;
TreeNode* p = root , *pre = NULL ,*node1 = NULL,*node2 = NULL;
while(p || !s.empty())
{
while( p )
{
s.push(p);
p = p -> left;
}
p = s.top();
s.pop();
if(pre && pre -> val > p -> val)
{
if( !node1 )node1 = pre;
node2 = p;
}
pre = p;
p = p -> right;
}
if(node1 && node2) swap(node1 -> val,node2 -> val);
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
