LintCode 두 갈래 나무 뒤집기

1. 설명
두 갈래 나무 한 그루를 뒤집다
어느 회사에서 너에게 이 문제를 물었니?
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. 요약
한 노드의 좌우 아이를 교환시키는 것은 그들의 값을 교환시키는 것이 아니라, 원래 왼쪽 아이를 가리키는 지침이다
오른쪽 아이를 가리키고, 오른쪽 아이를 가리키는 바늘은 왼쪽 아이를 가리킨다.

좋은 웹페이지 즐겨찾기