C++ 二叉树进阶：相关习题解析

2024-10-30 14:25:31

1. 二叉树创建字符串。

2. 二叉树的分层遍历1

3. 二叉树的分层遍历2

4. 二叉树的最近公共祖先

5. 将二叉搜索树转换为排序的双向链表

6. 从前序与中序遍历序列构造二叉树

7. 从中序与后序遍历序列构造二叉树

8. 二叉树的前序遍历，非递归迭代实现

9. 二叉树的中序遍历，非递归迭代实现

10. 二叉树的后序遍历，非递归迭代实现

1. 二叉树创建字符串。

. - 力扣（LeetCode）

初始化字符串并处理空树情况：

定义一个空字符串str用于存储结果。

首先检查输入的根节点是否为nullptr，如果是，则直接返回空字符串。

处理非空根节点：

如果根节点不为空，将根节点的值转换为字符串并添加到str中。

然后检查左子树是否存在：

如果左子树存在（root->left不为nullptr），在str中添加左括号(，递归调用tree2str处理左子树，并将结果添加到str中，最后再添加右括号)。

如果左子树不存在但右子树存在（root->left为nullptr但root->right不为nullptr），在str中添加()，以表示左子树为空但右子树存在。

接着检查右子树是否存在：
如果右子树存在（root->right不为nullptr），在str中添加左括号(，递归调用tree2str处理右子树，并将结果添加到str中，最后再添加右括号)。

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

2. 二叉树的分层遍历1

. - 力扣（LeetCode）

二叉树的层序遍历，多了一个条件，把每一层都存放在一个二维动态数组中，主要是控制每一层的个数，然后放入vector中，在把每个vector放入vector的vector中。

层序遍历：依靠队列来实现，当访问根的时候，出根节点，然后把该节点的左右节点分别入队，记住这里队列存储的是二叉树节点的指针，而不是该节点的值，这是因为在遍历的过程中，需要访问左右子节点。

遍历过程：当从队列中取出一个节点的时候，通过 front->val 获取该节点的值并存储在临时vector中

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

3. 二叉树的分层遍历2

. - 力扣（LeetCode）

该题和二叉树的分层遍历1是一样的，只需要把最后的存储在二维动态数组中的值逆序

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) 
    {
        vector<vector<int>> vv;
        queue<TreeNode*> q;
        if(root)
            q.push(root);
        while(!q.empty()) 
        {
            vector<int> v;
            int leveSize = q.size();
            for(int i = 0; i< leveSize; ++i) 
            {
                TreeNode* front = q.front();
                q.pop();
                v.push_back(front->val);
                if(front->left) 
                {
                    q.push(front->left);
                }
                if(front->right) 
                {
                    q.push(front->right);
                }
            }
            vv.push_back(v);
        }
        reverse(vv.begin(),vv.end());
        return vv;
    }
};

4. 二叉树的最近公共祖先

. - 力扣（LeetCode）

一、公共祖先的特征总结

当节点 p 是节点 q 的孩子时，当前节点就是祖先，反之亦然。这是因为在二叉树中，如果一个节点是另一个节点的直接子节点，那么它们的共同祖先就是父节点。

当 p 和 q 分别在当前节点的左右子树中时，当前节点就是它们的祖先。这是因为从根节点开始向下遍历，只有当两个节点分别位于不同子树时，当前节点才是它们的最低公共祖先。

二、情况 1：二叉搜索树

条件 a：

如果一个节点的值比当前节点小，另一个节点的值比当前节点大，那么当前节点就是它们的祖先。这是因为二叉搜索树的特性是左子树节点的值小于根节点的值，右子树节点的值大于根节点的值。所以当两个节点分别位于当前节点的两侧时，当前节点必然是它们的最低公共祖先。

例如，在一个二叉搜索树中，当前节点值为 10，p节点值为 5，q节点值为 15，那么当前节点就是 p 和 q 的最低公共祖先。

条件 b：

如果两个节点的值都比当前节点小，那么递归到左子树中去找祖先。因为二叉搜索树的特性，值小的节点必然在左子树中。

同理，如果两个节点的值都比当前节点大，那么递归到右子树中去找祖先。

例如，当前节点值为 10，p 节点值为 5，q 节点值为 8，那么需要在当前节点的左子树中继续查找它们的最低公共祖先。

三、情况 2：三叉链

在三叉链的情况下，类似于链表找交点问题。

四、情况 3：普通二叉树(该题目对应的情况)

条件 a：

当一个节点在当前节点的左子树，另一个节点在当前节点的右子树时，当前节点就是它们的祖先。这与公共祖先的特征一致，因为在普通二叉树中，没有特定的大小关系，只能通过遍历整个树来确定最低公共祖先。

例如，在一个普通二叉树中，当前节点有左子树和右子树，p 在左子树中，q 在右子树中，那么当前节点就是 p 和 q 的最低公共祖先。

条件 b：

如果两个节点都在左子树，递归到左子树中查找；如果两个节点都在右子树，递归到右子树中查找。这是因为在普通二叉树中，没有特定的顺序，只能通过逐步遍历子树来确定最低公共祖先。

例如，当前节点有左子树和右子树，p 和 q 都在左子树中，那么需要在当前节点的左子树中继续查找它们的最低公共祖先。

方法一：

这种方法比较直观，先判断节点是否在树中，然后再根据节点的位置来确定最低公共祖先

class Solution {
public:
    bool Find(TreeNode* root,TreeNode* x) 
    {
        if(root == nullptr)
            return false;
        return root == x || Find(root->left,x) || Find(root->right,x);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
       // 1,先看根节点是不是祖先
        if(root == nullptr || root == p || root == q)
            return root;
        bool pInLeft, pInRight, qInLeft, qInRight;
        pInLeft =  Find(root->left, p);
        pInRight = !pInLeft;
        qInLeft = Find(root->left,q);
        qInRight = !qInLeft;
        if((pInLeft && qInRight) || (qInLeft && pInRight)) 
            return root;
        if(pInLeft && qInLeft) 
           return lowestCommonAncestor(root->left,p,q);
        if(pInRight && qInRight) 
           return lowestCommonAncestor(root->right,p,q);
        return nullptr;
    }
};

方法二：

先看根是不是和 p 或者 q 中一个相等，如果不是相等，

假设在左子树中找到了 p，在右子树中找到没有找到，右子树这边返回 nullptr，所以左子树这边的值就是最近公共祖先。反之亦然。

如果一个在左边，一个在右边都有返回值，直接返回根。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        // 1. 先看根节点是不是祖先
        if (root == NULL || root == p || root == q) 
            return root;
        // 2. 如果根节点是祖先，有没有更近的祖先呢
        // 看看左子树
        struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
        // 看看右子树
        struct TreeNode* right = lowestCommonAncestor(root->right, p, q);
        // 3. 如果有的话显然只会在一侧 判断一下
        if (left == NULL) 
            return right;
        if (right == NULL) 
            return left;
        // 4. 如果没有更近的，默认还是返回root
        return root;
    }
};

接下来顺便把二叉搜索树的最近公共祖先这个题目也完成了，思路一样

. - 力扣（LeetCode）

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        if (root == nullptr || root == p || root == q)
            return root;
        if ((root->val > p->val && root->val < q->val) || (root->val > q->val && root->val < p->val))
            return root;
        if (p->val < root->val && q->val < root->val)
            return lowestCommonAncestor(root->left, p, q);
        if (p->val > root->val && q->val > root->val)
            return lowestCommonAncestor(root->right, p, q);
        return nullptr;
    }
};

5. 将二叉搜索树转换为排序的双向链表

. - 力扣（LeetCode）

链接中间关系（步骤①）
二叉搜索树的中序遍历（左 - 根 - 右）会产生一个有序的节点序列。在converList函数中，通过递归实现中序遍历。在遍历过程中，当处理每个节点时，利用一个引用参数prev来连接节点。例如，当prev不为nullptr时，prev - > right = cur和cur - > left = prev这两个操作就把当前节点cur和之前的节点prev双向连接起来。这样就按照中序遍历的顺序逐步构建了链表的中间部分。

找头节点和尾节点（步骤②）
由于中序遍历的第一个节点是最左节点，所以遍历二叉树找到最左节点作为链表的头节点是合理的。从逻辑上来说，这个最左节点在二叉搜索树中是值最小的节点。同样，在找到头节点后，通过不断地沿着节点的右指针移动，最终可以找到最右节点，它将作为链表的尾节点。

返回头节点（步骤③）
因为头节点是中序遍历的第一个节点，而中序遍历是升序排列节点值的，所以这个头节点的值是整个链表（也就是原来二叉搜索树中序遍历后的节点序列）中的最小值。返回头节点就可以作为整个循环双向链表的起始点，方便后续对链表进行操作。

class Solution {
public:
    void converList(Node* cur, Node*& prev) 
    {
        if(cur == nullptr) 
            return;
        converList(cur->left,prev);
        if(prev)
            prev->right = cur;
        cur->left = prev;
        prev = cur;
        converList(cur->right,prev);
    } 
    Node* treeToDoublyList(Node* root) 
    {
        Node* prev  = nullptr;
        converList(root,prev);
        Node* head = root;
        while(head && head->left)
            head = head->left;
        if(head == nullptr)
            return head;
        Node* tail = head;
        while(tail && tail->right) 
            tail =  tail->right;
        head->left = tail;
        tail->right = head;
        return head;
    }
};

6. 从前序与中序遍历序列构造二叉树

. - 力扣（LeetCode）

这个题目理解起来有一点抽象，画图结合代码理解就可以了。

一、解题关键

前序遍历的特点是先访问根节点，然后是左子树，最后是右子树。所以前序遍历结果中的第一个元素一定是整棵树的根节点。

中序遍历的特点是先访问左子树，然后是根节点，最后是右子树。通过在中序遍历中找到根节点的位置，可以确定左子树和右子树的元素范围。

二、构建步骤

首先，从前往后取前序遍历结果中的第一个元素，创建一个新的节点作为当前子树的根节点。

然后，在中序遍历结果中找到这个根节点的值，以确定左子树和右子树的范围。
在中序遍历中，根节点左边的元素构成左子树，右边的元素构成右子树。

接着，对于左子树：

根据确定的左子树范围，在前序遍历结果中找到对应左子树的起始位置（在前序遍历中，根节点后面的一段连续元素是左子树的前序遍历结果）。

递归调用构建函数，传入左子树的前序遍历和中序遍历结果以及对应的范围，构建左子树，并将构建好的左子树连接到根节点的left指针上。

对于右子树：

类似地，确定右子树在前序遍历中的起始位置（在前序遍历中，左子树部分之后的连续元素是右子树的前序遍历结果）。

递归调用构建函数，传入右子树的前序遍历和中序遍历结果以及对应的范围，构建右子树，并将构建好的右子树连接到根节点的right指针上。

重复以上步骤，直到所有子树都构建完成。

class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder,vector<int>& inorder,int& prei,int inbegin,int inend)
    {
        if(inbegin > inend)
            return nullptr;
        TreeNode* root  = new TreeNode(preorder[prei]);
        int rooti = inbegin;
        while(rooti <= inend)
        {
            if(preorder[prei] == inorder[rooti])
                break;
            else   
                ++rooti;
        }
        // [inbein,rooi-1] rooti [rooti+1,inend]
        if(inbegin <= rooti-1)
            root->left  = _buildTree(preorder,inorder, ++prei,inbegin,rooti-1);
        else
            root->left = nullptr;
        if(rooti + 1 <= inend) 
            root->right =  _buildTree(preorder,inorder, ++prei,rooti+1,inend);
        else
            root->right = nullptr;
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int prei = 0;
        int inbegin = 0, inend = inorder.size()-1;
        return _buildTree(preorder,inorder,prei,inbegin,inend);
    }
};

7. 从中序与后序遍历序列构造二叉树

. - 力扣（LeetCode）

注意点：

中序和后序遍历构建二叉树的情况
在通过中序和后序遍历构建二叉树时，后序遍历的顺序是 “左 - 右 - 根”。当构建右子树时，--end操作是为了更新后序遍历的索引，使其指向右子树的最后一个节点（在构建右子树的递归调用中）。因为后序遍历的特性，一旦处理完根节点（也就是当前正在构建的节点），下一个节点要么是右子树的根节点（如果有右子树），要么是左子树的根节点（如果没有右子树）。在构建右子树后，end已经指向了左子树的最后一个节点，不需要额外的--end操作就可以正确地开始构建左子树。

中序和前序遍历构建二叉树的情况（推测你这里的prev是类似prei用于前序遍历索引）
前序遍历的顺序是 “根 - 左 - 右”。在构建二叉树的递归过程中，每次构建一个子树时，需要先处理根节点，然后是左子树，最后是右子树。当构建左子树时，++prei操作是为了将索引移动到左子树的根节点（在前序遍历序列中）。而在构建右子树时，同样需要++prei操作来将索引移动到右子树的根节点，因为前序遍历序列中左子树节点之后才是右子树节点。这是由于前序遍历的顺序决定的，需要不断更新索引来按照正确的顺序获取子树的根节点。

class Solution {
public:
    TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& end, int inbegin, int inend) {
        if (inbegin > inend) 
            return nullptr;
        TreeNode* root = new TreeNode(postorder[end]);
        int rooti = inbegin;
        while (rooti <= inend) {
            if (inorder[rooti] == postorder[end]) 
                break;
            else 
                ++rooti;
        }
        root->right = _buildTree(inorder, postorder, --end, rooti + 1, inend);
        root->left = _buildTree(inorder, postorder, end, inbegin, rooti - 1);
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int end = postorder.size() - 1;
        return _buildTree(inorder, postorder, end, 0, inorder.size() - 1);
    }
};

8. 二叉树的前序遍历，非递归迭代实现

. - 力扣（LeetCode）

一、递归写法

class Solution 
{
public:
    void _preorderTraversal(TreeNode* root, vector<int>& v) 
    {
        if(root == nullptr)
            return;
        v.push_back(root->val);
        _preorderTraversal(root->left,v);
        _preorderTraversal(root->right,v);
    }
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        _preorderTraversal(root,ret);
        return ret;
    }
};

二、非递归写法

整体过程

创建一个空的结果向量ret用于存储遍历结果。

创建一个栈st用于辅助遍历。

使用一个指针cur指向当前正在处理的节点。

进入循环，只要当前节点不为空或者栈不为空，就继续循环。

第一个内部while循环用于遍历左子树：

只要当前节点cur不为空，就将其值加入结果 ret，表示访问了该节点（先访问根节点）。

将当前节点压入栈中，为后续访问右子树做准备。

将当前节点指向其左子树，继续遍历左子树。

当左子树遍历完后，当前节点cur为空，此时从栈中弹出一个节点top，这个节点是上一个被访问的节点的父节点。

将当前节点cur指向弹出节点的右子树，进行下一轮循环，开始遍历右子树。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        stack<TreeNode*> st;
        TreeNode * cur = root;
        while(cur || !st.empty()) 
        {
            //1、先访问树的左路节点
            //2、再访问左路节点的左子树
            while(cur)
            {
                ret.push_back(cur->val);
                st.push(cur); //为了访问右子树
                cur = cur->left;
            }
            //取栈中的左路节点的右子树出来访问
            TreeNode* top = st.top();
            st.pop();   
            cur = top->right;  //迭代
        }
        return ret;
    }
};

9. 二叉树的中序遍历，非递归迭代实现

. - 力扣（LeetCode）

与前序遍历类似，就存在一些细微的不同，就是访问顺序。(唯一变化的就是访问节点的时机)

左路节点先不访问，只入栈，然后访问根，再访问左路节点的右子树。

右子树通过迭代的方式再分成左路节点和左路节点的右子树的方式访问。

1、左路节点(入栈)
2、取栈中的节点，(访问节点+访问节点的右子树)

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        stack<TreeNode*> st;
        TreeNode* cur =  root;
        while(cur || !st.empty()) 
        {
            //1、左路节点入栈，先不能访问(中序)
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            //2、取出栈中节点，访问和节点的右子树
            TreeNode* top = st.top();
            st.pop();
            ret.push_back(top->val);
            cur =  top->right;
        }
        return ret;
    }
};

10. 二叉树的后序遍历，非递归迭代实现

. - 力扣（LeetCode）

还是一样的，只不过访问的时机不一样

左路节点的访问，所以还需要加一个条件：右为空可以访问，右访问过了，也可以访问

通过一个指针 lastNode 记录上一次访问的节点，以确定何时处理当前节点。如果不加这个指针处理，就是重复拿到栈中的左路节点的值

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

码农公寓

1. 二叉树创建字符串。

2. 二叉树的分层遍历1

3. 二叉树的分层遍历2

4. 二叉树的最近公共祖先

5. 将二叉搜索树转换为排序的双向链表

6. 从前序与中序遍历序列构造二叉树

7. 从中序与后序遍历序列构造二叉树

8. 二叉树的前序遍历，非递归迭代实现

9. 二叉树的中序遍历，非递归迭代实现

10. 二叉树的后序遍历，非递归迭代实现

相关文章