文章/答案/技术大牛

发布

社区首页 >专栏 >【题目/训练】二叉树的创建&&遍历（递归&&非递归）

【题目/训练】二叉树的创建&&遍历（递归&&非递归）

IsLand1314

发布于 2024-10-15 12:02:19

17800

代码可运行

文章被收录于专栏：学习之路学习之路

运行总次数：0

代码可运行

节点类的二叉树实现

1. 根据二叉树创建字符串

思路：在正常前序递归遍历的基础上，单独加上一个考虑到右子树为空的情况，如下：其结果为 1（2（4（5）（6））），当遍历到节点2时由于2的左节点不为空，右节点为空，我们应该先打印根节点，然后打印（左子树）。

class Solution {
public:
    string tree2str(TreeNode* root) {
        if(root == nullptr) return "";
        if(root->left == nullptr && root->right == nullptr) return to_string(root->val);
        if(root->right == nullptr) 
            return to_string(root->val) + "(" + tree2str(root->left) + ")";
        return to_string(root->val) + "(" + tree2str(root->left) + ")(" +tree2str(root->right) + ")";

    }
};

2. 二叉树的层序遍历

思路： 方法一BFS： 用队列来写，把每一层入队列，出队列的第一个头节点，然后把头节点所连节点加入队列中，然后循环往复，直到队列没有元素 方法二DFS： 定义一个k，ans[k]表示每层的节点数组。

方法一： BFS

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
       vector<vector<int>> vv;
       if(root == NULL) return vv;
       queue<TreeNode*> q;
       q.push(root);
       while(!q.empty())
       {
            vector<int> v;
            int size = q.size();
            while(size--)
            {
                TreeNode* node = q.front();
                q.pop();
                v.emplace_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            vv.push_back(v);
       }
       return vv;
    }
};

方法二：DFS

class Solution {
public:
    void dfs(TreeNode* root, int k, vector<vector<int>>& ans)
    {
        if (root == NULL) return;
        if (k == ans.size()) ans.push_back(vector<int>());
        ans[k].push_back(root->val);
        dfs(root->left, k + 1, ans);
        dfs(root->right, k + 1, ans);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        dfs(root, 0, ans);
        return ans; 
    }
};

3. 二叉树的层序遍历II

思路： 这道题要求从下到上输出每一层的节点值，只要在层序遍历I稍作修改即可：在遍历完一层节点之后，将存储该层节点值的列表添加到结果列表的头部。

方法一、BFS

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> vv;
        if(root == nullptr) return vv;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            vector<int> v;
            int n = q.size(); //每一层的节点
            while(n--)
            {
                TreeNode* Node = q.front();
                q.pop();
                v.push_back(Node->val);
                if(Node->left) q.push(Node->left);
                if(Node->right) q.push(Node->right);
            }
            vv.push_back(v);
        }
        reverse(vv.begin(),vv.end());
        return vv;
    }
};

方法二：DFS

class Solution {
public:
    void dfs(TreeNode* root, int k, vector<vector<int>>& ans)
    {
        if (root == NULL) return;
        if (k == ans.size()) ans.push_back(vector<int>());
        ans[k].push_back(root->val);
        dfs(root->left, k + 1, ans);
        dfs(root->right, k + 1, ans);
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        dfs(root, 0, ans);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

4. 二叉树最近公共祖先

思路： 两个节点 p,q 分为两种情况： 1、 p 和 q 在相同子树 2、p 和 q 在不同子树 从根节点遍历，递归向左右子树查询节点信息。 递归终止条件：如果当前节点为空或等于 p 或 q，则返回当前节点 递归遍历左右子树，如果左右子树查到节点都不为空，则表明 p 和 q 分别在左右子树中，因此，当前节点即为最近公共祖先； 如果左右子树其中一个不为空，则返回非空节点。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL || root == p || root == q) return root;
        TreeNode* l = lowestCommonAncestor(root->left, p, q); //若在左子树则不为空
        TreeNode* r = lowestCommonAncestor(root->right, p, q); //若在右子树则不为空
        if(l && r) return root; //不在同一棵子树
        return l ? l : r; //在同一棵子树，则返回子树的根节点，即 p 或者 q
    }
};

5. 二叉搜索树和双向链表

思路： 1、已知将二叉搜索树进行中序遍历可以得到由小到大的顺序排列，因此本题最直接的想法就是进行中序遍历。 2、将中序遍历的结果用数组存储下来，得到的数组是有从小到大顺序的。最后将数组中的结点依次连接即可。 3、但是根据题目的要求1，不能创建新的结点，而上述方法的数组中存储的其实是结点，并不满足题意；所以需要在中序遍历的过程中，直接对结点的指针进行调整。 4、调整的思路如下：（1）使用一个指针preNode指向当前结点root的前继。（例如上述图中root为指向10的时候，preNode指向8）（2）对于当前结点root，有root->left要指向前继preNode（中序遍历时，对于当前结点root，其左孩子已经遍历完成了，此时root->left可以被修改。）；同时，preNode->right要指向当前结点（当前结点是preNode的后继），此时对于preNode结点，它已经完全加入双向链表。

class Solution {
public:
	TreeNode* preNode; //前继节点
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(pRootOfTree == nullptr) return pRootOfTree;
		TreeNode* p = pRootOfTree;
		while(p->left) p = p->left; //找到双向链表的开头。
		Inorder(pRootOfTree);
		return p;
		
    }
	void Inorder(TreeNode* root){
		if(root == nullptr) return;
		Inorder(root->left);
		root->left = preNode;
		if(preNode) preNode->right = root;
		preNode = root;//更新preNode，指向当前结点，作为下一个结点的前继。
		Inorder(root->right);
	}
};

6. 前序遍历非递归

给你二叉树的根节点 root ，返回它节点值的前序遍历。

AC代码如下：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(root == nullptr) return ans;
        stack<TreeNode*> st;
        TreeNode* node = root;
        while(!st.empty() || node != nullptr)
        {
            while(node!=nullptr) {
                ans.push_back(node->val);
                st.push(node);
                node=node->left;
            }
            node = st.top();
            st.pop();
            node = node->right;
        }
        return ans;
    }
};

7. 中序遍历非递归

给定一个二叉树的根节点 root ，返回它的中序遍历

AC代码如下

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> s;
        while(root != nullptr || !s.empty()){
            while(root != nullptr){
                s.push(root);
                root = root->left;
            }
            root = s.top(); //取出第一个元素
            s.pop();
            ans.push_back(root->val);
            root = root -> right;
        }
        return ans;
    }
};

8. 后序遍历非递归

AC代码如下：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> s;
        TreeNode* pre = nullptr;
        while(root != nullptr || !s.empty()){
            while(root != nullptr){
                s.push(root);
                root = root->left;
            }
            root = s.top(); //取出第一个元素
            s.pop();
            if (root->right == nullptr || root->right == pre) {
                ans.push_back(root->val);
                pre = root;
                root = nullptr;
            } 
            else {
                s.push(root);
                root = root->right;
            }
        }
        return ans;
    }
};

9. 从前序遍历和中序遍历序列构建二叉树

思路：由于前序遍历的性质可知其第一个节点为根节点，然后我们通过该根节点，再将中序遍历结果分开，再来找节点，如下图所示然后用DFS来解决即可

class Solution {
private:
    unordered_map<int, int> pos;

public:
    TreeNode* dfs(const vector<int>& preorder, const vector<int>& inorder, int pl, int pr, int il, int ir) {
        if (pl > pr) return nullptr;
        
        // 前序遍历中的第一个节点就是根节点
        int k = pos[preorder[pl]]; // 在中序遍历中定位根节点

        // 先把根节点建立出来
        TreeNode* root = new TreeNode(preorder[pl]);
        int len = k - il;// 得到左子树中的节点数目

        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root->left = dfs(preorder, inorder, pl + 1, pl + len, il, k - 1);

        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root->right = dfs(preorder, inorder, pl + len + 1, pr, k + 1, ir);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        // 构造哈希映射，帮助我们快速定位根节点
        for (int i = 0; i < n; ++i) {
            pos[inorder[i]] = i;
        }
        return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

10. 从中序和后序遍历序列构建二叉树

和上面代码思路差不多

AC代码如下：

class Solution {
public:
    unordered_map<int, int> pos;
    TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int il, int ir, int pl, int pr){
        if(il > ir) return nullptr; //递归截止
        int k = pos[postorder[pr]]; //中序遍历确立根位置
        TreeNode* root = new TreeNode(postorder[pr]); //创立根节点
        root->left = dfs(inorder, postorder, il, k - 1, pl, pl + k - 1 - il);
        root->right = dfs(inorder, postorder, k + 1, ir, pl + k - il, pr - 1);
        return  root;        

    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        for(int i = 0; i < n; i++){
            pos[inorder[i]] = i; //标记二叉树祖先遍历结果所对应下标
        }
        return dfs(inorder, postorder, 0, n - 1, 0 , n - 1);
    }
};

11. 根据前序和后序遍历构造二叉树

思路： 前序遍历为：

(根结点)(前序遍历左分支)(前序遍历右分支)

而后序遍历为：

(后序遍历左分支)(后序遍历右分支)(根结点)

这题我们主要用到dfs的想法然后我们定义两个全局变量，preIndex，postIndex来分别表示当前前序遍历和后序遍历，遍历到哪一个节点，然后由于前序遍历的第一个节点就是根节点，我们先存下根节点，然后在后序遍历找到对应根节点的左右子树，然后返回根节点即可。

AC代码如下：

class Solution {
public:
    int preIndex = 0,posIndex = 0;
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        TreeNode* root = new TreeNode(preorder[preIndex++]);
        if(root->val != postorder[posIndex]) 
            root->left = constructFromPrePost(preorder, postorder);
        if(root->val != postorder[posIndex]) 
            root->right = constructFromPrePost(preorder, postorder);
        posIndex++;
        return root;

    }
};

数组类的二叉树遍历

1. 求先序排列

思路：主要思路和节点类中的从中序和后序遍历构建二叉树基本相同，通过后序遍历取最后一位可以得到当前子树的根节点为：A，然后到中序遍历里面取寻找这个根节点，从而可以通过中序遍历来将当前树分割成左子树和右子树。 然后递归重复这个过程就可以得到先序遍历。要注意递归的条件要l1>r1，因为在边界处可以会出现l1>r1的情况这时候要直接结束这一层递归。 但是由于这个是字符串输入，故有两种方法，第一种就是用下标来进行和上面类似，而第二种就是用substr来进行

AC代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

string in, post;

//方法一：
void dfs1(int il, int ir, int pl, int pr){
	if (il > ir) return;
	char root = post[pr];
	cout << root; //输出根节点
	int pos;
	//在in中找到root出现的位置 
	for (pos = il; pos <= ir; pos++) {
		if (in[pos] == root) break;
	}
	dfs1(il, pos - 1, pl, pl + pos - 1 - il);
	dfs1(pos + 1, ir, pl + pos - il, pr - 1);

}

//方法二：
void dfs2(string s1, string s2){
	int len1 = s1.length(); // len1就相当于方法一的ir-il
	int len2 = s2.length();
	if (len1 <= 0) return;
	
	char root = s2[len2 - 1]; //根节点
	cout << root;//每次递归输出根节点 
	int pos = s1.find(root); //在s1中找到ch出现的位置 
	dfs2(s1.substr(0, pos), s2.substr(0, pos)); //递归左子树 
	dfs2(s1.substr(pos + 1), s2.substr(pos, len1 - pos - 1)); //递归右子树
}

int main(){
	cin >> in >> post;
	int n = in.size();
	//dfs1(0, n - 1, 0, n - 1);
	dfs2(in, post);
	return 0;
}

2. 中序和后序遍历数组，输出层序

//给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。输入格式：输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。输出格式：在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。输入样例： 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 输出样例： 4 1 6 3 5 7 2

AC代码如下：

#include <iostream>
#include <queue>
#include <string>
using namespace std;

const int N = 35;
int b[N], c[N]; //后序遍历，中序遍历
int l[N], r[N]; //左子树，右子树
int n;
queue<int> q;

int dfs(int x1, int y1, int x2, int y2)
{
    if (x1 > y1) return 0;
    int pos = x1, root = c[y2]; //找到中序遍历的根节点

    while (b[pos] != root) pos++;

    //前序遍历结果
    l[root] = dfs(x1, pos - 1, x2, x2 + pos - x1 - 1);
    r[root] = dfs(pos + 1, y1, x2 + pos - x1, y2 - 1);

    return root;
}

void bfs(int root)
{
    int flag = 0;
    q.push(root);

    while (!q.empty())
    {
        int i = q.front();
        q.pop();

        if (flag) printf(" %d", i);
        else {
            flag = 1;
            printf("%d", i);
        }

        if (l[i] != 0) q.push(l[i]);
        if (r[i] != 0) q.push(r[i]);
    }
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++) cin >> c[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    int root = dfs(0, n - 1, 0, n - 1);
    bfs(root);

    return 0;
}

3. 中序序列

思路： 和节点类的11题不同的是，我们这里由于无法直接弄其的左右子树，而且只想知道一棵树的前序遍历和后序遍历是求不出中序遍历的。但是，因为题目多了一个条件【若某节点只有一个子结点，则此处将其看作左儿子结点】。所以可以求出唯一的一个中序遍历。在二叉树的前序遍历中，第一个数字总是树的根结点，根结点右边的第一个结点总是左儿子结点。在该二叉树的后序遍历中，知道了该根结点和其左儿子在后序遍历中的下标后，夹在根结点和其左儿子之间的结点是根结点的右子树。在左儿子的左边部分结点是该左儿子的子树。

既然我们已经找到了左、右子树的前序遍历和中序遍历，我们可以用同样的方法分别取构建左右子树。也就是说，接下来可以用递归的方法完成。

class Solution {
public:
    int len = 0;
    void dfs(vector<int>& pre,  int pl, int pr, vector<int>& suf, int sl, int sr, vector<int>& ans)
    {
        if (pl > pr || sl > sr) return; //区间不存在
        if (pl == pr) //区间内只有一个节点
        {
            ans[len++] = pre[pl];
           return;
        }
        int pos = -1;
        for (int i = sl; i <= sr; i++) {
            if (suf[i] == pre[pl + 1]) //在后序遍历中找到根节点左儿子的位置
                pos = i; 
        }
        
        dfs(pre, pl + 1, pos - sl + pl + 1, suf, sl, pos, ans); //左子树
        ans[len++] = pre[pl];
        dfs(pre, pos - sl + pl + 2, pr, suf, pos + 1, sr - 1, ans); //右子树


    }
    vector<int> solve(int n, vector<int>& pre, vector<int>& suf) {
        vector<int> ans(n);
        dfs(pre, 0, n - 1, suf, 0, n - 1, ans);
        return ans;
    }
};