二叉树编程经验
遍历
层序遍历
BFS
如下是使用BFS层序遍历,并获取二叉树深度的方法,使用队列辅助遍历。新进队列的是出队列节点的左右节点。
int TreeDepth(TreeNode* pRoot) {
deque<TreeNode*> deq;
deq.push_back(pRoot);
TreeNode *temp;
int elem_n = 1;
int depth = 0;
if (pRoot==nullptr) return 0;
while(elem_n!=0){
for(int i=1;i<=elem_n;++i){
temp = deq.front();
deq.pop_front();
if (temp->left!=nullptr)
deq.push_back(temp->left);
if (temp->right!=nullptr)
deq.push_back(temp->right);
}
depth += 1;
elem_n = deq.size();
}
return depth;
}
需要对层序遍历进行分割以确定每层的元素时可以使用如下方案
class Solution {
public:
vector<vector<int>> Print(TreeNode* root) {
if(root==nullptr) return {};
vector<vector<int>> v;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int size=q.size();
vector<int> temp;
//每一层的遍历
while(size--){
TreeNode * node=q.front();
temp.push_back(node->val);
q.pop();
if(node->left){
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
v.push_back(temp);
}
if(v.size()>=1000){
return {};
}
return v;
}
};
前序、中序、后序遍历
以下是使用中序遍历访问从小到大的第k个元素
递归法
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param proot TreeNode类
* @param k int整型
* @return int整型
*/
int count=0;//标记现在是第几个数
vector<int> res;
int KthNode(TreeNode* proot, int k) {
// write code here
if (proot==nullptr||k==0) return -1;
++count;
KthNode(proot->left, k);
res.push_back(proot->val);
//if(count==k) return proot->val;
KthNode(proot->right, k);
return res.size()>=k?res[k-1]:-1;
}
};
DFS
使用栈辅助遍历
int KthNode(TreeNode* proot, int k) {
// write code here
//todo K > treeNodeNumber
if(NULL == proot ){
return -1;
}
//stack<TreeNode*> s = new stack<TreeNode*>();
//stack<TreeNode*> s = new stack<TreeNode*>();
//C++ sytle declaration;
stack<TreeNode*> s;
int i =0;
while( !s.empty() || proot !=NULL ){
if( NULL!= proot){
s.push(proot);
proot = proot->left;
}else{
//已经左到底了
proot = s.top();//get top
s.pop();
//仅仅下面这4行是定制行为
i++;
if( k== i)
{return proot->val;
}
proot = proot->right;
}
}
return -1;
}
};