[刷题]二叉树专题

发表于 | 更新于 | 评论数：
本文字数： 42k | 阅读时长 ≈ 38 分钟

参考 几道和「二叉树」有关的算法面试题

1. [Leetcode 105] 从前序与中序遍历序列构造二叉树 (剑指OFFER面试题 7)

  • 解法：递归，由先序序列确定子树根节点，由中序序列确定当前节点下的子树范围。
  • 主要参数(递归函数)：先序序列的起点idx与终点idx， 中序序列的起点idx与终点idx。
  • 递归停止条件： 先序序列或中序序列的起点idx > 终点idx。
  • 递归参数更新方法：
    • 左子树更新:
      • 先序起点idx+1。 preL + 1
      • 先序终点为中序确定左子树节点数量num + 先序起点idx。 preL + num
      • 中序起点为之前递归层中的中序起点。 inL
      • 中序终点为根节点在中序序列中的idx - 1。 inRoot - 1
    • 右子树更新:
      • 先序起点idx+1 + 中序确定左子树节点数量num。 preL + num + 1
      • 先序终点为之前递归层中的先序终点。 preR
      • 中序起点为根节点在中序序列中的idx + 1。 inRoot + 1
      • 中序终点为为之前递归层中的中序终点。 inR 
        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
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        /**
         * Definition for a binary tree node.
         * struct TreeNode {
         *     int val;
         *     TreeNode *left;
         *     TreeNode *right;
         *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
         * };
         */
        class Solution {
        public:
            TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
                if(preorder.empty()|| inorder.empty())
                    return nullptr;
                
                return TreeIterate(0, preorder.size() - 1, 0, inorder.size() - 1, preorder, inorder);
                
            }
            
            TreeNode* TreeIterate(int preL, int preR, int inL, int inR, const vector<int>& preorder, const vector<int>& inorder){
                if(preL > preR || inL > inR)
                    return nullptr;
                
                int inRoot = 0; //中序遍历根节点位置
                // vector<int>::iterator inRootIter =find(inorder.begin(), inorder.end(), preorder[preL]); 
                // int inRoot std::distance(std::begin(inorder), inRootIter);
                for(int i = 0; i < inorder.size(); i++)
                {
                    if(preorder[preL] == inorder[i]){
                        inRoot = i;
                        break;
                    }
                }
                int num = inRoot - inL; //中序确定左子树节点数量
                
                TreeNode* currNode = new TreeNode(preorder[preL]);
                currNode -> left = TreeIterate(preL + 1, preL + num, inL, inRoot - 1 , preorder, inorder);
                currNode -> right = TreeIterate(preL + num + 1, preR, inRoot + 1, inR, preorder, inorder);
                return currNode;
            }
        };

2. [Leetcode 572] 另一个树的子树 (剑指Offer面试题 26)

  • 解法：递归寻根相同，根相同后判断子树是否相同。

  • 注意：停止条件，空指针处理

  • 代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
    public:
        bool isSame(struct TreeNode* s, struct TreeNode* t)
        {
            if(!s && !t) // 两个子树叶子都是空
                 return true;
            if(!s || !t) // 有一个不是空
                return false;
            if(s->val != t->val)
                return false;
            return isSame(s->left,t->left) && isSame(s->right,t->right);
        }
        bool isSubtree(struct TreeNode* s, struct TreeNode* t) {
            if(!s) // 主树为空
                return false;
            if((s->val == t->val) && isSame(s,t))
                return true;
            return isSubtree(s->left,t) || isSubtree(s->right,t);
        }
    };

3. [LeetCode 144] 二叉树的前序遍历

  • 解法：

    • 递归，先输出再递归

    • 循环，用栈模拟，节点右子节点入栈，左节点直接输出。

      å‡ é“å’Œã€ŒäºŒå‰æ ‘ã€æœ‰å…³çš„ç®—æ³•é¢è¯•é¢˜

  • 代码：

    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
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    /////====递归解
    class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
            vector<int> res;
            if(root == nullptr) return {};
         
            Recurrence(res, root);
            return res;
        }
     
        void Recurrence(vector<int> &res, TreeNode* root){
            if(root == nullptr) return;
            res.emplace_back(root->val);
            Recurence(res, root->left);
            Recurence(res, root->right);
        }
    };

    ////====循环解 前序：根左右，stack(根 右 左)
    class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
            if(!root) return {};
            vector<int> res;
            stack<TreeNode* > transStack;
            transStack.push(root);
            
            while(!transStack.empty()){
                TreeNode* curr = transStack.top();
                transStack.pop();
                res.emplace_back(curr->val);
                if(curr->right)
                    transStack.push(curr->right);
                
                if(curr->left)
                    transStack.push(curr->left);
            }
            return res;
        }
    };

4. [LeetCode 94] 二叉树的中序遍历

  • 解法：

    • 递归：遍历左节点后输出值

    • 循环：

      å‡ é“å’Œã€ŒäºŒå‰æ ‘ã€æœ‰å…³çš„ç®—æ³•é¢è¯•é¢˜

  • 代码：

    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
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode* root) {
            vector<int> res;
            if(root == nullptr) return {};
            Recurrence(res, root);
            return res;
        }
        
        void Recurrence(vector<int>& res, TreeNode* root){
            if(root == nullptr){
                return;  
            } 
            
            Recurrence(res, root->left);
            res.emplace_back(root->val);
            Recurrence(res, root->right);
        }
    };

    //循环解(当前节点不是空就一直往栈里push左孩子，如果当前节点为空，则出栈，当前节点设为出栈节点的右节点)
    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode* root) {
            if(root == nullptr) return {};
            
            vector<int> res;
            stack<TreeNode* > transStack;
            TreeNode* curr = root;

            while(curr||!transStack.empty()){
                if (curr) {
                    transStack.push(curr);
                    curr = curr->left;
                } else {
                    curr = transStack.top();
                    transStack.pop();
                    res.emplace_back(curr->val);
                    curr = curr->right;
                }          
            }
          
            return res;
        }
    };

5. [Leetcode 145] 二叉树的后序遍历

  • 解法：递归/循环，循环解，先左插，再右插，遇到空节点出栈，出栈元素插在结果数组的最前面。

    å‡ é“å’Œã€ŒäºŒå‰æ ‘ã€æœ‰å…³çš„ç®—æ³•é¢è¯•é¢˜

  • 代码:

    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
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    // 数组
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            if(!root) return {};
            vector<int> res;
            stack<TreeNode*> transStack;
            TreeNode* curr = root;
            transStack.push(root);
            
            while(!transStack.empty()){
                curr = transStack.top();
                transStack.pop();
                if(curr->left) transStack.push(curr->left);
                if(curr->right) transStack.push(curr->right);
                res.insert(res.begin(), curr->val);
                
            }
            return res;
        }
    };

    // 链表转换 （Leetcode上的时间表现一样）
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            if(!root) return {};
            
            list<int > resList;
            stack<TreeNode*> transStack;
            TreeNode* curr = root;
            transStack.push(root);
            
            while(!transStack.empty()){
                curr = transStack.top();
                transStack.pop();
                if(curr->left) transStack.push(curr->left);
                if(curr->right) transStack.push(curr->right);
                resList.insert(resList.begin(), curr->val);
                
            }
            vector<int> res(resList.begin(), resList.end());
            return res;
        }
    };

5. [LeetCode 226] 翻转二叉树 (剑指Offer面试题27)

  • 解法：递归换序

  • 代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    public:
        TreeNode* invertTree(TreeNode* root) {
            if(root == nullptr) return nullptr;
            
            TreeNode* left = invertTree(root->left);
            TreeNode* right = invertTree(root->right);
            
            root->right = left;
            root->left = right;
            
            return root;
        }   
    };

6.[LeetCode 101] 对称二叉树 (剑指Offer面试题28)

  • 解法1： 递归，

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            return isSymmetrical(root, root);
        }
        
        bool isSymmetrical(TreeNode* pRoot1, TreeNode* pRoot2){
            if(pRoot1==nullptr && pRoot2==nullptr) return true;
            if(pRoot1==nullptr || pRoot2 == nullptr) return false;
            if(pRoot1->val != pRoot2->val) return false;
            return isSymmetrical(pRoot1->left, pRoot2->right) && isSymmetrical(pRoot1->right, pRoot2->left);
        }
        

    };

  • 解法2：BFS循环

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            if(!root) return true;
            stack<TreeNode*> Q;
            Q.push(root->left);
            Q.push(root->right);
            while(!Q.empty()){
                TreeNode* r1=Q.top();Q.pop();
                TreeNode* r2=Q.top();Q.pop();
                if(!r1 && !r2) continue;
                if(r1 && r2){
                    if(r1->val != r2->val) return false;
                    Q.push(r1->left);Q.push(r2->right);
                    Q.push(r1->right);Q.push(r2->left);
                }else return false;
            }
            return true;
        }
    };

7. [Leetcode 102] 二叉树的层次遍历 (剑指Offer面试题32)

  • 思路：用一个队列nodeQ维护二叉树BFS顺序，由于题目中需要分层记录，所以需要维护每一层的数据vectorlayerRes以及每一层可扩展节点队列layerQ。

  • 代码：

    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
    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            if(root == nullptr ) return {};
            queue<TreeNode* > nodeQ;
            vector<vector<int>> res;
            nodeQ.push(root);
            while(!nodeQ.empty()){
                vector<int> layerRes;
                int qSize = nodeQ.size();

                while(qSize--){
                    TreeNode* currNode = nodeQ.front();
                    nodeQ.pop();
                    layerRes.emplace_back(currNode->val);
                    if(currNode->left)
                        nodeQ.push(currNode->left);
                    if(currNode->right)
                        nodeQ.push(currNode->right);
                }
              
                res.emplace_back(layerRes);
            }
            return res;
        }
    };

8. [Leetcode 230] 二叉搜索树中第K小的元素

  • 解法: 循环模拟中序遍历

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    public:
        int kthSmallest(TreeNode* root, int k) {
            stack<TreeNode*> transStack;
            while(1){
                if(root != NULL){
                    transStack.push(root);
                    root = root->left;
                } else {
                    if(--k == 0){
                        return transStack.top()->val;
                    } else {
                        root = (transStack.top())->right;
                        transStack.pop();
                    }
                }
            }
        }
    };

本文标题:[刷题]二叉树专题

文章作者:zhkmxx930

发布时间:2019年02月07日 - 21:02

最后更新:2019年03月19日 - 11:03

原始链接:https://zhkmxx9302013.github.io/post/76e180f5.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

一分钱也是爱，mua~