LintCode 두 갈래 나무 뒤집기
두 갈래 나무 한 그루를 뒤집다
어느 회사에서 너에게 이 문제를 물었니?
Airbnb Alibaba Amazon Apple Baidu Bloomberg Cisco Dropbox Ebay Facebook Google Hulu Intel Linkedin Microsoft NetEase Nvidia Oracle Pinterest Snapchat Tencent Twitter Uber Xiaomi Yahoo Yelp Zenefits
피드백 감사합니다.
예제
1 1
/ \ / \
2 3 => 3 2
/ \
4 4
2. 분석
두 갈래 나무를 뒤집으면 모든 노드의 좌우 아이를 교환할 수 있다. 만약에 한 노드가 현재 노드의 왼쪽 아이가 오른쪽 아이로 변하더라도
오른쪽 아이가 왼쪽 아이가 되다.전체 두 갈래 나무의 뒤집기는 바로 뿌리 노드를 뒤집은 후 조작한 노드를 뿌리 노드의 좌우 아이로 바꾸는 것이다.
이것은 매우 전형적인 귀속 조작이다. 한 노드의 회전은 그 후에 모든 노드가 이렇다.
3. 코드
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
void invertBinaryTree(TreeNode *root) {
//write your code here
TreeNode *temp;
if(root==NULL) return;
else
{
temp=root->left;//좌우 아이를 바꾸다
root->left=root->right;
root->right=temp;
invertBinaryTree(root->left);//작업하는 노드를 아래로 이동하여 최종적으로 모든 노드에 대한 회전 작업을 완성하다
invertBinaryTree(root->right);
}
}
};
4. 요약
한 노드의 좌우 아이를 교환시키는 것은 그들의 값을 교환시키는 것이 아니라, 원래 왼쪽 아이를 가리키는 지침이다
오른쪽 아이를 가리키고, 오른쪽 아이를 가리키는 바늘은 왼쪽 아이를 가리킨다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.