iOS实现反转二叉树（前序遍历二叉树）

article/2025/9/4 22:29:06

题目:

Input:
在这里插入图片描述

Output:
在这里插入图片描述

首先分析下这个二叉树,从上往下看发现这个树是把树上的数据进行了交换,但是仔细一看发现最后一排的1-3反转过去后变成了3-1.所以得出结论,这道题是左右子树进行了交换,用函数递归就能很容易实现了.

## OC版本

声明节点属性：

#import <Foundation/Foundation.h>NS_ASSUME_NONNULL_BEGIN@interface TreeNodel : NSObject- (instancetype)initWithVal:(NSInteger)val;@property (strong, nonatomic) TreeNodel *left;
@property (strong, nonatomic) TreeNodel *right;
@property (assign, nonatomic) NSInteger val;@endNS_ASSUME_NONNULL_END

实现代码：

/// 反转二叉树
/// @param root 二叉树
- (TreeNodel *)invertTree:(TreeNodel *)root
{//递归调用有一个明确的出口if (!root) {return root;}//不满足条件时自己调用自己[self invertTree:root.left];[self invertTree:root.right];[self exchangeNode:root];return root;
}- (void)exchangeNode:(TreeNodel *)node {if (node) {TreeNodel *temp = node.left;node.left = node.right;node.right = temp;}
}

测试：

- (void)viewDidLoad {[super viewDidLoad];TreeNodel *one = [[TreeNodel alloc]initWithVal:4];one.left = [[TreeNodel alloc]initWithVal:2];one.right = [[TreeNodel alloc]initWithVal:7];TreeNodel *two = one.left;two.left = [[TreeNodel alloc]initWithVal:1];two.right = [[TreeNodel alloc]initWithVal:3];TreeNodel *there = one.right;there.left = [[TreeNodel alloc]initWithVal:6];there.right = [[TreeNodel alloc]initWithVal:9];NSLog(@"层次遍历 = %@",[self leveold:one]);NSLog(@"反转之后层次遍历 = %@",[self leveold:[self invertTree:one]]);}

结果：
在这里插入图片描述

后记：
前序遍历二叉树：

/// 二叉树的前序遍历
/// @param node 二叉树
- (NSArray *)preorderTravelsal:(TreeNodel *)node{NSMutableArray *res = [NSMutableArray array];NSMutableArray *stack = [NSMutableArray array];while (node != nil || stack.count > 0) {if (node != nil) {[res addObject:@(node.val)];[stack addObject:node];node = node.left;}else{TreeNodel *lastNode = stack.lastObject;node = lastNode.right;[stack removeLastObject];}}return res;
}

结果：
在这里插入图片描述