面试题 17.12. BiNode

发布时间:2023年12月26日

二叉树数据结构TreeNode可用来表示单向链表(其中left置空,right为下一个链表节点)。实现一个方法,把二叉搜索树转换为单向链表,要求依然符合二叉搜索树的性质,转换操作应是原址的,也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

注意:本题相对原题稍作改动

示例:

输入: [4,2,5,1,3,null,6,0]
输出: [0,null,1,null,2,null,3,null,4,null,5,null,6]

不产生新的树节点,直接改动树的左右叶子节点,效率更高的会考虑使用新的树节点,在遍历的直接连接叶子节点,效率会更高。

/**
 * 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:
    vector<TreeNode*> vc;
    void walkTree(TreeNode* root)
    {
        if(root==nullptr)
            return;
        else
        {
            walkTree(root->left);
            vc.push_back(root);
            walkTree(root->right);
        }
    } 
    TreeNode* convertBiNode(TreeNode* root) 
    {
        if(root==nullptr)
            return nullptr;
        walkTree(root);
        int n= vc.size();
        for(int i=0;i< n;i++)
        {
            if(i+1<n)
            {
                vc[i]->left=nullptr;
                vc[i]->right=vc[i+1];
            }
            if(i+1==n)
            {
                vc[i]->left= nullptr;
                vc[i]->right= nullptr;
            }
        }
        return vc[0];
    }
};

文章来源:https://blog.csdn.net/Doubao93/article/details/135231667
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。