前序遍历和后序遍历的代码区别

前序的递归函数的 返回值为空；参数部分含有结果值；return；后续的递归函数的 返回值为求值的类型； 参数部分不含有结构值； return 类型+1；

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例： 给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。

递归法思路：求最大深度，应该是前序遍历，但是最大深度也可以是高度，因此用后序遍历也可以

int maxDepth(TreeNode* root){ if(root==NULL) return 0; return getDepth(root); } int getDepth(TreeNode* cur){ if(cur==NULL) return 0; int leftdepth=getDepth(cur->left); int rightdepth=getDepth(cur->right); return max(leftdepth,rightdepth)+1; }

迭代法思路：层序遍历最适合，因为遍历的次数就是层数就是最大深度

int maxDepth(TreeNode* root) {//层序遍历 queue<TreeNode*> que; int depth=0; if(root!=NULL) que.push(root); while(!que.empty()){ int size=que.size(); depth++; for(int i=0;i<size;i++){ TreeNode* cur=que.front(); que.pop(); if(cur->left) que.push(cur->left); if(cur->right) que.push(cur->right); } } return depth; }

559. N叉树的最大深度

给定一个 N 叉树，找到其最大深度。 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 例如，给定一个 3叉树 : 我们应返回其最大深度，3。 int maxDepth(Node* root) {//层序遍历 queue<Node*> que; int depth=0; if(root!=NULL) que.push(root); while(!que.empty()){ int size=que.size(); depth++; for(int i=0;i<size;i++){ Node* cur=que.front(); que.pop(); for(int j=0;j<cur->children.size();j++){ if(cur->children[j]) que.push(cur->children[j]); } } } return depth; } int maxDepth(Node* root) {//递归 return getmax(root); } int getmax(Node* node){ if(node==NULL) return 0; int depth=0; for(int i=0;i<node->children.size();i++){ depth=max(depth,getmax(node->children[i])); } return depth+1; }

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7

迭代思路：比较好想的是用层序遍历来遍历结点，判断每一个结点是不是叶结点，如果是叶结点，那么就结束遍历，当前层数就是最小深度

int minDepth(TreeNode* root) { int depth=0; queue<TreeNode*> que; if(root!=NULL) que.push(root); while(!que.empty()){ int size=que.size(); depth++; for(int i=0;i<size;i++){ TreeNode* cur=que.front(); que.pop(); if(cur->left) que.push(cur->left); if(cur->right) que.push(cur->right); if(cur->left==NULL&&cur->right==NULL) return depth; } } return depth; }

递归思路：和求最大深度的思路相似，但是需要注意的地方在于，当根结点的左结点或者右结点为空的时候，min()为0，但其实最小深度不为0，而是另外一个子树的最小深度。 错误：

int minDepth(TreeNode* root) { } int getDepth(TreeNode* cur){ if(cur==NULL) return 0; int left=getDepth(cur->left); int right=grtDepth(cur->right); return min(left,right)+1; }

正确：

int minDepth(TreeNode* root) { return getDepth(root); } int getDepth(TreeNode* cur){ if(cur==NULL) return 0; if(cur->left==NULL&&cur->right!=NULL) return 1+getDepth(cut->right); if(cur->right==NULL&&cur->left!=NULL) return 1+getDepth(cut->left); int left=getDepth(cur->left); int right=grtDepth(cur->right); return min(left,right)+1; }

222. 完全二叉树的节点个数

给出一个完全二叉树，求出该树的节点个数。 说明： 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。 示例: 输入: 1 / \ 2 3 / \ / 4 5 6 输出: 6

递归思路：左边结点个数加上右边结点个数

class Solution1 {//递归 public: int countNodes(TreeNode* root) { return getNodeNum(root); } int getNodeNum(TreeNode* root){ if(root==NULL) return 0; int leftNum=getNodeNum(root->left); int rightNum=getNodeNum(root->right); return leftNum+rightNum+1; } };

迭代思路；层序遍历统计每层个数

class Solution {//迭代 public: int countNodes(TreeNode* root) { int num=0; queue<TreeNode*> que; if(root!=NULL) que.push(root); while(!que.empty()){ int size=que.size(); num+=size; for(int i=0;i<size;i++){ TreeNode* cur=que.front(); que.pop(); if(cur->left) que.push(cur->left); if(cur->right) que.push(cur->right); } } return num; } };

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 返回 false 。

递归思路：比较每一个结点的高度，显然用后序遍历，比较当前结点的左右子树的最大高度，大于1则不平衡 不容易想到的一点是，如果差大于1就不应返回高度，而是返回一个不可能的值，主函数判断是不是这个值，如果是则就返回false；

bool isBalanced(TreeNode* root) { if(root==NULL) return true; return getdiff(root)==-1?false:true; } int getdiff(TreeNode* cur){ if(cur==NULL) return 0; int left=getdiff(cur->left); if(left==-1){return -1;} int right=getdiff(cur->rigth); if(right==-1){return -1;} //当结点的差不为1时，就不用返回高度了； return abs(left-right)>1?-1:max(left,right)+1; }