Good questions —— 二叉树篇

算法
字数统计: 1.8k   |   阅读时长≈ 8 分钟

概述：本文记录了刷题过程中与二叉树相关的优质题目及解题思路

二叉树的前中后序遍历

前序遍历

（1）递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//递归
class Solution {
public:
    vector<int> res;
    vector<int> preorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }
    void dfs(TreeNode* node){
        if(node==nullptr) return;
        res.push_back(node->val);
        dfs(node->left);
        dfs(node->right);
    }
};

（2）迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//迭代
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(root==nullptr)
        return {};
        vector<int> res;
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()){
            TreeNode* temp=stk.top();
            stk.pop();       //必须先pop出来
            res.push_back(temp->val);//根节点先push到结果数组中
            if(temp->right) stk.push(temp->right);//注意先push right节点到栈中，为了让left节点到栈顶先pop出来
            if(temp->left)  stk.push(temp->left);
        }
        return res;
    }
};

（3）风格统一的迭代写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//迭代2 用这种写法与中序风格统一
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(root==nullptr)
        return {};
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* cur= root;
        while(!stk.empty() || cur!=nullptr){
            //前序遍历在节点入栈时即可直接将val放到res中
            if(cur!=nullptr){
                res.push_back(cur->val);
                stk.push(cur);
                cur=cur->left;
            }
            else{//当访问到最底层时
                //关键步骤，理解cur的改变
                cur=stk.top()->right;
                stk.pop();
            }
        }
        return res;
    }
};

中序遍历

（1）递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//递归
class Solution {
public:
    vector<int> res;
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }
    void dfs(TreeNode* root){
        if(root==nullptr) return;
        dfs(root->left);
        res.push_back(root->val);
        dfs(root->right);
    }
};

（2）迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//逻辑比较清晰直观的版本，思路很清楚！
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        auto p = root;

        // 左链入栈循环
        // 这个循环你会发现和后面的的循环代码有一部分重复，你可以进行合并。
        // 但是这样你就需要在后面循环条件多加一个判断 while (p || !st.empty())，代码也会变得稍微没那么直观
        while (p != nullptr) {
            stk.push(p);
            p = p->left;
        }
        
        while (!stk.empty()) {
            auto node = stk.top();
            stk.pop();
            res.emplace_back(node->val);
            p = node->right;
            // 一旦弹出一个节点，继续做“左链入栈”操作
            while (p) {
                stk.push(p);
                p = p->left;
            }
        }   
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//整合优化代码后的版本
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* cur=root;
        while(!stk.empty()||cur!=nullptr){
            // 指针来访问节点，访问到最底层
            if(cur!=nullptr){
                // 将访问的节点放进栈
                stk.push(cur);
                cur=cur->left;
            }
            else{
                //从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                res.push_back(stk.top()->val);//中
                cur=stk.top()->right;
                stk.pop();
            }
        }
        return res;
    }
};

后序遍历

（1）递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//递归
class Solution {
public:
    vector<int> res;
    vector<int> postorderTraversal(TreeNode* root) {
        //1.确定终止条件
        if(root==nullptr)
        return res;
        //前中后序遍历只需要改换这三条的顺序
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        res.push_back(root->val);
        return res;
    }
};

（2）迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//迭代2 可与前中后序相应写法风格相统一，思想是中右左顺序遍历，最后reverse
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(root==nullptr) return {};
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* cur= root;
        while(!stk.empty() || cur!=nullptr){
            if(cur!=nullptr){
                res.push_back(cur->val);
                stk.push(cur);
                cur=cur->right;  //注意这里是right,前序是left
            }
            else //当访问到最底层时{
                //关键步骤，理解cur的改变
                cur=stk.top()->left; //这里是left，前序是right
                stk.pop();
            }
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

重建二叉树

从前序和中序遍历序列构造二叉树

思路：

（1）明白前序遍历的第一个节点永远是根节点

（2）用哈希表记录中序遍历中每个节点值对应的索引位置

（3）结合（1）（2）可知根节点在中序遍历中的位置，从而可以知道左子树和右子树的大小

（4）递归地进行左右子树的构建，函数返回根节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    unordered_map<int,int> mp;      //{value, index in inorder array}
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();    //两个数组长度相等
        for(int i=0;i!=inorder.size();++i){
            mp[inorder[i]] = i;
        }
        TreeNode* root = rebuild(preorder,inorder,0,n-1,0,n-1);
        return root;
    }

private:
    TreeNode* rebuild(vector<int>& pv,vector<int>& iv,int pl,int pr, int il, int ir){
        //注意不要落下递归的终止条件
        if(pr<pl) return nullptr;
        //前序遍历的第一个节点即为根节点
        TreeNode* root = new TreeNode(pv[pl]);
        //在中序遍历中找到对应根节点，即可知道左子树和右子树的大小
        int leftsize = mp[pv[pl]] - il;
        root->left = rebuild(pv,iv,pl+1,pl+leftsize,il,il+leftsize-1);
        root->right = rebuild(pv,iv,pl+leftsize+1,pr,il+leftsize+1,ir);
        return root;
    }
};

从中序遍历和后序遍历序列构造二叉树

思路近似，都是要计算出左右子树的大小，然后进行递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    unordered_map<int,int> mp;      //{value, index in inorder array}
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();    //两个数组长度相等
        for(int i=0;i!=inorder.size();++i){
            mp[inorder[i]] = i;
        }
        TreeNode* root = rebuild(inorder,postorder,0,n-1,0,n-1);
        return root;
    }
private:
    TreeNode* rebuild(vector<int>& iv,vector<int>& pv,int il,int ir, int pl, int pr){
        //注意不要落下递归的终止条件
        if(ir<il) return nullptr;
        //后序遍历的最后一个节点即为根节点
        TreeNode* root = new TreeNode(pv[pr]);
        //在中序遍历中找到对应根节点，即可知道左子树和右子树的大小
        int leftsize = mp[pv[pr]] - il;
        root->left = rebuild(iv,pv,il,il+leftsize-1,pl,pl+leftsize-1);
        root->right = rebuild(iv,pv,il+leftsize+1,ir,pl+leftsize,pr-1);
        return root;
    }
};

二叉搜索树中第k小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

思路：

（1）要反应过来二叉搜索树的中序遍历即为一个升序数组

（2）取升序数组中的第k个就行

如果要搜索第k大的元素，其实只要调整一下遍历的顺序，先遍历右子树，再遍历左子树即可

二叉树中节点和最大的路径

  1. 求二叉树中节点之和最大的路径，必须至少包含一个节点

思路：

（1）关键就是想清楚递归的返回值：应该返回包含当前节点在内的并且最多只包含左右子树其中之一边的最大路径。

（2）在递归的过程中不断更新一个最大路径和，包含当前节点并且可以同时包含左右子树的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return maxsum;
    }
    int dfs(TreeNode* root){
        if(root==nullptr) return 0;
        int lval = max(0,dfs(root->left));//包含根节点root的单条路径的最大值
        int rval = max(0,dfs(root->right));
        maxsum = max(maxsum,root->val+lval+rval);
        return root->val + max(lval,rval);
    }
private:
    int maxsum = INT_MIN;
};
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2022 ZHU
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信