镜像二叉树（递归/非递归）

约定不等于承诺〃 2022-05-09 13:42 232阅读 0赞

镜像二叉树：根节点的左右孩子交换  
            所有节点的左右孩子都交换  
例如：  
![在这里插入图片描述][70]

## 递归 ##

递推公式：根节点的左子树和右子树换位置  
终止条件：空树

void MirrorTree(BNode *root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		BNode *tmp = root->left;
    		root->left = root->right;
    		root->right = tmp;
    		MirrorTree(root->left);
    		MirrorTree(root->right);
    	}

## 非递归 ##

如果用非递归，就要用到循环和栈，先进后出。  
第一步：先将根节点压栈  
第二步：保存栈顶元素并出栈  
第三步：将栈顶元素的左右孩子换位置  
第四步：判断左右孩子是否为空，如果不是空，压栈  
**注：一定要记得出栈，要不然就会变成死循环**

void MirrorTree2(BNode *root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		Stack stack;
    		StackInit(&stack);
    		StackPush(&stack, root);
    		while (!StackEmpty(&stack))
    		{
    			BNode *node = StackTop(&stack);
    			StackPop(&stack);
    	
    			BNode *tmp = node->left;
    			node->left = node->right;
    			node->right = tmp;
    	
    			if (node->left)
    			{
    				StackPush(&stack, node->left);
    			}
    			if (node->right)
    			{
    				StackPush(&stack, node->right);
    			}
    		}
    	}

[70]: /images/20220506/b76e40cf14524bc1a362fff833edf14b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，232人围观）

还没有评论，来说两句吧...

相关阅读

相关求二叉树镜像 -- 采用递归和非递归方法

/求二叉树镜像 -- 采用递归和非递归方法经调试可运行源码及分析如下： / include <stdlib.h> include <i

左手的ㄟ右手/ 2022年07月28日 11:55/ 0 赞/ 184 阅读

相关求二叉树深度 -- 递归和非递归实现

/求二叉树深度 -- 采用递归和非递归方法经调试可运行源码及分析如下： / include <stdio.h> include <st

曾经终败给现在/ 2022年07月28日 09:46/ 0 赞/ 172 阅读

相关镜像二叉树，递归

二叉树的镜像参与人数：6974时间限制：1秒空间限制：32768K [ 算法知识视频讲解][Link 1] 题目描述操作给定的二叉树，将其变换为源二叉

- 日理万妓/ 2022年07月19日 02:40/ 0 赞/ 164 阅读

相关数据结构之搜索二叉树递归&非递归

一.搜索二叉树的性质> 1). 每个节点都有一个作为搜索依据的关键码(key),所有节点的关键码互不相同。 2). 左子树上所有节点的关键码(key)都小于根节点的关键

曾经终败给现在/ 2022年07月16日 12:28/ 0 赞/ 213 阅读

相关二叉树递归非递归

include <iostream> include <string.h> include <stack> include <windows.

ゞ浴缸里的玫瑰/ 2022年07月14日 07:43/ 0 赞/ 222 阅读

相关镜像二叉树（递归/非递归）

镜像二叉树：根节点的左右孩子交换所有节点的左右孩子都交换例如： ![在这里插入图片描述][70] 递归递推公式：根节点的左子树

约定不等于承诺〃/ 2022年05月09日 13:42/ 0 赞/ 233 阅读

相关非递归、递归遍历二叉树！

树的先、中、后、层序的遍历，需要用到栈结构和队结构。首先来看树本身的定义： typedef char TElemType; typedef struct BiTNod

小鱼儿/ 2022年04月13日 10:29/ 0 赞/ 373 阅读

相关 leetcode 226. 翻转二叉树（递归与非递归）

题目描述翻转一棵二叉树。示例：输入：

迷南。/ 2022年02月24日 21:16/ 0 赞/ 188 阅读

相关二叉树递归和非递归遍历

二叉树递归和非递归遍历 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly

拼搏现实的明天。/ 2021年12月17日 04:07/ 0 赞/ 366 阅读

相关【数据结构】（二叉树）求非空二叉树的宽度递归&&非递归

求非空二叉树的宽度方法一递归： > \\算法思想：\\当我们看图的时候我们可以知道求二叉树的宽度本质就是求其一层有多少个结点那么如何用递归的方式去计算每一层结点的个

女爷i/ 2021年11月09日 10:10/ 0 赞/ 430 阅读