剑指offer之树专题

1、层次遍历（bfs)

非递归

每一层是按照从左到右的顺序

为了满足先遍历先出采用队列的数据结构,队列里面存放我们遍历过的节点

 

首先根节点入队，当队列不空时，出队队首元素并打印相应节点的内容。如果出队的节点有左孩子或者右孩子，则入队左孩子节点或者右孩子节点，如此循环

class Solution
{
public:
    vector<int> bfs(TreeNode *root)//返回的是一个int的vector
    {
        vector<int>res;
        queue<TreeNode *>q;//辅助队列
 
        if(root==NULL)return res;//空树返回空
        q.push(root);//将根节点入队
      
 
        while(!q.empty())
        {
            //入队
            res.push_back(q.front()->val);
            if(q.front()->left!=NULL)
            {
                q.push(q.front()->left);
            }
            if(q.front()->right!=NULL)
            {
                q.push(q.front()->right);
            }
            // 出队
            q.pop();//弹出第一个元素
        }
        return res;//只有最后才会执行这个
    }
};

2、深度优先遍历（递归）

按照遍历顺序将节点存放在容器中

遍历就像我们走路上有很多坑，一旦掉进去就是很多层，只有到底才能开始慢慢向上攀爬，小事件结束就是我们的梯子

 1、确定终止条件

如果当层遍历的节点为空的话，就是结束本层，返回上一层

if(cur == NULL) return;

 2、单层递归的逻辑：前序是中、左、右

vec.push_back(cur ->val);//中间节点插入
traversal(cur ->left,vec);//左
traversal（cur ->right,vec）;//右

完整代码

lass Solution {
public:
    void preorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) return;//终止条件
        
        res.push_back(root->val);    //中
        preorder(root->left, res);   //左
        preorder(root->right, res);  //右
    }
 
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
};
8

非递归

利用栈

访问到空节点的话，就会跳到上一层，然后将栈顶出

我们栈是先进后出

前序是中，右、左（）

中序：左、中、右（）

后续：中、左、右

//前序代码

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        if(root == nullptr)  return res;
 
		s.push(root);  //压入根结点
        while (!s.empty()){  //入栈是 根右左
            TreeNode* node = s.top();  s.pop();
            res.push_back(node->val);                 //中
            if (node->right) stk.push(node->right);   //右
            if (node->left)  stk.push(node->left);    //左
        }
 
        return res;
    }
};