擦边球网站怎么做,扬州公司做网站,遂平网站建设,网页素材网站免费普通二叉树的结点数#xff1a;
递归法#xff1a;
对二叉树进行前序or后序遍历#xff1a;
typedef struct Tree
{int data;Tree* leftChild;Tree* rightChild;
}tree,*linklist;
//计算普通二叉树的结点数
int nodenums(linklist node)
{if(node nullptr) return 0; …普通二叉树的结点数
递归法
对二叉树进行前序or后序遍历
typedef struct Tree
{int data;Tree* leftChild;Tree* rightChild;
}tree,*linklist;
//计算普通二叉树的结点数
int nodenums(linklist node)
{if(node nullptr) return 0; //node为空就返回0int leftnums nodenums(node-leftChild); //左子树的数量通过递归计算出来int rightnums nodenums(node-rightChild); //右子树的数量通过递归计算出来return leftnums rightnums 1;返回左子树的数量 右子树的数量 1(根结点的数量)
} 化简写法
typedef struct Tree
{int data;Tree* leftChild;Tree* rightChild;
}tree,*linklist;
//计算普通二叉树的结点数
int nodenums(linklist node)
{if(node nullptr) return 0;return 1 nodenums(node-leftChild) nodenums(node-rightChild);
} 队列法
利用BFS的思想层序遍历
#include queue
typedef struct Tree
{int data;Tree* leftChild;Tree* rightChild;
}tree,*linklist;
//法二(BFS)
int coutnode(linklist node)
{queuelinklist q; //建立新的linklist型队列qif(node nullptr) q.push(node); //如果node不为空就把结点node推进队列int result 0;//result用来存结点数//BFS层序遍历while(q.empty()){int size q.size();for(int i 0;i size;i){linklist p q.front();q.pop();result; //记录结点数if(p-leftChild) q.push(node-leftChild);if(p-rightChild) q.push(node-rightChild);}}return result;
}
完全二叉树的结点数
完全二叉树的本身会包含满二叉树可以简便写先判断最大的满二叉树的位置然后再利用普通二叉树的递归遍历方法进行计算。
如果遇到满二叉树则返回满二叉树的结点数可以利用公式2^n-1利用位运算(2 n) - 1。
(n为深度)也可以利用我前面的文章讲述的快速幂利用递归求出二次幂。
int nodenum(linklist node)
{if(node nullptr) return 0;linklist left node-leftChild;linklist right node-rightChild;//左右子树深度int leftdepth 0;int rightdepth 0;while(left){left left-leftChild;leftdepth;}while(right){right right-rightChild;rightdepth;}//如果左右子树的深度相等就是满二叉树if(leftdepth rightdepth) return (2 leftdepth) - 1;//满二叉树的计算结点公式2^n-1return 1 nodenum(node-leftChild) nodenum(node-rightChild);
} 判断平衡二叉树
二叉树中任意结点的左右子树的深度相差不超过 1那么它就是一棵平衡二叉树 。
所以abs(左子树深度 - 右子树深度) 1就不是平衡二叉树。
所以先按照最大深度的计算方法递归左右子树的最大深度然后判断是否符合平衡二叉树如果不是就return返回false最后return返回平衡二叉树的最大深度。
typedef struct Tree
{int data;Tree* leftChild;Tree* rightChild;
}tree,*linklist;
//如果不是平衡二叉树那么就返回-1记录其不是平衡二叉树
int balancedepth(linklist node)
{int leftdepth balancedepth(node-leftChild);if(leftdepth -1) return -1;int rightdepth balancedepth(node-rightChild);if(rightdepth -1) return -1;if(abs(leftdepth - rightdepth) 1) return -1;//不平衡return 1 max(leftdepth , rightdepth);
} 输入一棵二叉树的根结点判断该树是不是平衡二叉树。 如果某二叉树中任意结点的左右子树的深度相差不超过 1那么它就是一棵平衡二叉树。 注意 规定空树也是一棵平衡二叉树。 数据范围 树中节点数量 [0,500]。 样例 输入二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示5/ \7 11/ \12 9输出true struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:bool isBalanced(TreeNode* root) {int res dfs(root);if(res ! -1) return true;else return false;}int dfs(TreeNode* root){if(!root) return 0;int leftdepth dfs(root-left),rightdepth dfs(root-right);if(leftdepth -1 || rightdepth -1) return -1;if(abs(rightdepth - leftdepth) 1) return -1;return 1 max(leftdepth , rightdepth);}
};
今天内容到这里了感谢收看。
