drupal wordpress,烟台软件优化网站,aso优化推广,建设银行官网app目录 一、翻转二叉树
1.1 题目链接
1.2 题目描述
1.3 解题思路
二、二叉树最大深度
2.1 题目链接
2.2 题目描述
2.3 解题思路
三、二叉树中序遍历
3.1 题目链接
3.2 题目描述
3.3 解题思路 一、翻转二叉树
1.1 题目链接
翻转二叉树
1.2 题目描述 1.3 解题思路
根…目录 一、翻转二叉树
1.1 题目链接
1.2 题目描述
1.3 解题思路
二、二叉树最大深度
2.1 题目链接
2.2 题目描述
2.3 解题思路
三、二叉树中序遍历
3.1 题目链接
3.2 题目描述
3.3 解题思路 一、翻转二叉树
1.1 题目链接
翻转二叉树
1.2 题目描述 1.3 解题思路
根据题目很显然得出我们就只需要交换除了根的节点的左右孩子。我们这里采用递归解决问题那么递归的结束条件又是什么呢当该节点是空节点时就结束。思路就是这样我们来动手实现一下。 struct TreeNode
{int val;struct TreeNode *left;struct TreeNode *right;
};struct TreeNode* invertTree(struct TreeNode* root)
{if(root NULL)return NULL;struct TreeNode* temp root-left;root-left root-right;root-right temp;if(root-left)invertTree(root-left);if(root-right)invertTree(root-right);return root;
}
二、二叉树最大深度
2.1 题目链接
二叉树最大深度
2.2 题目描述 2.3 解题思路
在上面解决翻转二叉树问题时我们就用到了递归。在解决二叉树的题目通常都会使用到递归大家要好好的复习一下递归。我们把这颗二叉树拆解成根和左右子树后面把左右子树也当作根来继续拆解直到根为空节点时就不再进行拆解。递归的结束条件就是根为空节点因为是最大深度所以我们需要比较左右子树的高度我们可以定义一个指针来计入高度为什么用指针因为要改变计数器要影响到外面那为什么不用全局变量呢全局变量比较麻烦也可以采用另外一种。本人比较懒就采用了另外一种。
struct TreeNode
{int val;struct TreeNode *left;struct TreeNode *right;
};int maxDepth(struct TreeNode* root)
{if(root NULL)return 0;int left maxDepth(root-left);int right maxDepth(root-right);return left right? left1:right1;
} 三、二叉树中序遍历
3.1 题目链接
二叉树中序遍历
3.2 题目描述 3.3 解题思路
还是老样子采用递归来解决首先我们要知道中序是什么中序是先遍历 左子树、根、再到右子树根据题目知道我们要返回遍历并且计入了中序顺序的二叉树。只有完全二叉树和满二叉树我们才会采用数组进行实现一般情况我们都是采用链表的结构来实现二叉树那我们就需要开辟空间了。我们就会存在一个问题应该开辟多少空间合适呢可以和之前实现单向链表一样开辟一点点后续不够继续申请空间这里我有一个不一样的方法那就是我们计算得到有多少个节点就开辟多少个空间。struct TreeNode* root, int* returnSize 题目给了我们两个参数其中一个是二叉树那另外一个参数有什么用呢我感觉int* returnSize是类似一个计数的参数。因为要返回遍历并且计入了中序顺序的二叉树所以我们可以定义一个数组来储存。那我们就需要封装成另外一个函数来实现了 void preorder(struct TreeNode* root, int* res ,int* returnSize)函数目的实现中序遍历后的储存数据。我们要好好的体会一下中序遍历的写法 左子树 、根 、右子树。
计算二叉树节点个数
int TreeSize(struct TreeNode* root)//计算二叉树节点个数
{return root NULL ? 0 :TreeSize(root-left) TreeSize(root-right) 1;
}
实现中序遍历后的储存数据
void preorder(struct TreeNode* root, int* res ,int* returnSize)
{if(root NULL){return;}preorder(root-left, res ,returnSize);//左res[(*returnSize)]root-val;//根preorder(root-right, res ,returnSize);//右
} void preorder(struct TreeNode* root, int* res ,int* returnSize)
{if(root NULL){return;}preorder(root-left, res ,returnSize);//左res[(*returnSize)]root-val;//根preorder(root-right, res ,returnSize);//右
}int TreeSize(struct TreeNode* root)
{return root NULL ? 0 :TreeSize(root-left) TreeSize(root-right) 1;
}int* inorderTraversal(struct TreeNode* root, int* returnSize)
{int size TreeSize(root);int* res malloc(sizeof(int) * size);*returnSize 0;preorder(root, res, returnSize);return res;
}
