[검지 Offer 학습] [면접 문제 19: 두 갈래 나무의 거울]

2159 단어

제목:


함수를 완성하고 두 갈래 트리를 입력하십시오. 이 함수는 거울을 출력합니다.

생각:


이전에 이 나무의 모든 결점을 두루 훑어보았는데, 만약 두루 훑어본 결점에 자결점이 있다면, 그것의 두 자결점을 교환해라.모든 비잎결점의 좌우 결점을 교환한 후 나무의 거울을 얻었다.

코드:


트리 노드:
#import 
//  
@interface NSBinaryTreeNode : NSObject
//  
@property (nonatomic, strong) NSString *value;
//  
@property (nonatomic, strong) NSBinaryTreeNode *left;
//  
@property (nonatomic, strong) NSBinaryTreeNode *right;
@end

#import "NSBinaryTreeNode.h"
#import 

void mirrorBinaryTree (NSBinaryTreeNode *binaryTreeNode) {
    
    if (binaryTreeNode == nil) {
        return;
    }
    
    NSBinaryTreeNode *tmpTreeNodel = binaryTreeNode.left;
    binaryTreeNode.left = binaryTreeNode.right;
    binaryTreeNode.right = tmpTreeNodel;
    
    mirrorBinaryTree(binaryTreeNode.left);
    
    mirrorBinaryTree(binaryTreeNode.right);
}

//       
void printBinaryTree (NSBinaryTreeNode *headerTreeNode) {
    if (headerTreeNode != nil) {
        printBinaryTree(headerTreeNode.left);
        NSLog(@"%@ ", headerTreeNode.value);
        printBinaryTree(headerTreeNode.right);
    }
}


int main(int argc, const char * argv[]) {
    @autoreleasepool {

        //       8
        //    /    \
        //   6     10
        //  / \   / \
        // 5   7 9  11
        NSBinaryTreeNode *root = [NSBinaryTreeNode new];
        root.value = @"8";
        root.left = [NSBinaryTreeNode new];
        root.left.value = @"6";
        root.left.left = [NSBinaryTreeNode new];
        root.left.left.value = @"5";
        root.left.right = [NSBinaryTreeNode new];
        root.left.right.value = @"7";
        root.right = [NSBinaryTreeNode new];
        root.right.value = @"10";
        root.right.left = [NSBinaryTreeNode new];
        root.right.left.value = @"9";
        root.right.right = [NSBinaryTreeNode new];
        root.right.right.value = @"11";
        printBinaryTree(root);
        mirrorBinaryTree(root);
        printBinaryTree(root);
    }
    return 0;
}

좋은 웹페이지 즐겨찾기