从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(中)

简介: 从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145

从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(上):https://developer.aliyun.com/article/1521948


解析代码:(法一)

class Solution {
public:
    bool Find(TreeNode* sub,TreeNode* x)
    {
        if(sub == nullptr)
        {
            return false;
        }
        return sub == x 
        || Find(sub->left,x) 
        || Find(sub->right,x);
    }
 
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == p || root == q) // 只要其中一个是自己自己,自己就是公共祖先
        {
            return root;
        }
        bool pInLeft,pInRight,qInLeft,qInRight;
        pInLeft = Find(root->left,p);
        pInRight = !pInLeft; // 依题意,p不在左边就在右边
 
        qInLeft = Find(root->left,q);
        qInRight = !qInLeft; // 同上
 
        if((pInLeft && qInRight) || (qInLeft && pInRight))
        {
            return root; // 如果一个在左边,一个在右边,自己就是祖先
        }
        else if(pInLeft && qInLeft) // 如果两个都在左边,递归去左边
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        else // 只剩两个都在右边的情况
        {
            return lowestCommonAncestor(root->right,p,q);
        }
    }
};

法一的时间复杂度是O(H*N)H是树的高度,N是树的结点数,怎么优化到O(N)?

解析代码:(法二)

我们把要找的结点的所有祖先都用栈存起来,

(按前序找,不确定是不是就入栈,确定不是就pop掉继续找)

然后转化为链表相交问题:

class Solution {
public:
    bool FindPath(TreeNode* root,TreeNode* x,stack<TreeNode*>& path)
    {
        if(root == nullptr)
            return false;
 
        path.push(root); // 不管是不是,先入栈
        if(root == x)
            return true; // 找到返回true
        if(FindPath(root->left,x,path))
            return true; // 左树找到返回true
        if(FindPath(root->right,x,path))
            return true; // 右树找到返回true
        path.pop(); // 都找不到
        return false;
    }
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath,qPath;
        FindPath(root,p,pPath);
        FindPath(root,q,qPath);
 
        while(pPath.size() != qPath.size()) // 类似链表相交
        {
            if(pPath.size() > qPath.size())
            {
                pPath.pop();
            }
            else
            {
                qPath.pop();
            }
        }
        while(pPath.top() != qPath.top())
        {
            pPath.pop();
            qPath.pop();
        }
        return pPath.top(); // 相等,返回其中一个
    }
};

剑指 Offer 36. 二叉搜索树与双向链表 - 力扣(LeetCode)

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。

为了让您更好地理解问题,以下面的二叉搜索树为例:

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

注意:本题与主站 426 题相同:力扣

注意:此题对比原题有改动。

(牛客一道差不多的题的链接:)

二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)

解析代码:(牛客)

/*
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
  TreeNode(int x) :
      val(x), left(NULL), right(NULL) {
  }
};*/
class Solution {
public:
    void InOrderConvert(TreeNode* cur, TreeNode*& prev) // 希望就有一个prev,传引用
  {
    if(cur == nullptr)
    {
      return;
    }
    InOrderConvert(cur->left,prev);
    cur->left = prev; // 走到中序这,知道cur的left和prev的right
    if(prev)
    {
      prev->right = cur;
    }
    prev = cur; // 往后走
    InOrderConvert(cur->right,prev);
  } 
 
    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* prev = nullptr;
    InOrderConvert(pRootOfTree,prev);
 
    TreeNode* head = pRootOfTree;
    while(head && head->left) // 找链表的头结点
    {
      head = head->left;
    }
    return head;
    }
};

解析代码:(力扣)

力扣的就是在牛客的基础上改成双向链表:(要判空了)

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node() {}
    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }
    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    void treeToDoublyListInOrder(Node* cur,Node*& prev)
    {
        if(cur == nullptr)
    {
      return;
    }
    treeToDoublyListInOrder(cur->left,prev);
    cur->left = prev; // 走到中序这,知道cur的left和prev的right
    if(prev)
    {
      prev->right = cur;
    }
    prev = cur; // 往后走
    treeToDoublyListInOrder(cur->right,prev);
    }
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr)
        {
            return nullptr;
        }
 
        Node* prev = nullptr;
        treeToDoublyListInOrder(root,prev);
 
        Node* head = root;
        while(head && head->left) // 找链表的头结点
        {
            head = head->left;
        }
        Node* tail = root; // 变成双向循环链表
        while(tail && tail->right)
        {
            tail = tail->right;
        }
        head->left = tail;
        tail->right = head;
        return head;
    }
};

105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode)

难度中等

给定两个整数数组 preorderinorder ,其中 preorder 是二叉树的先序遍历inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。


示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]

输出: [-1]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorderinorder无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
 
    }
};

解析代码:

class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int left, int right)
  {
    if (left > right)
    {
      return nullptr;
    }
    TreeNode* root = new TreeNode(preorder[prei++]); // 先构建好根
    int ini = left; // 分割中序
    while (ini <= right)
    {
      if (inorder[ini] == root->val)
      {
        break;
      }
      else
      {
        ini++;
      }
    }
    // [left,ini-1] ini [ini+1,right] 构建好根之后,构建根的左右子树
        root->left = _buildTree(preorder, inorder, prei, left, ini - 1);
    root->right = _buildTree(preorder, inorder, prei, ini + 1, right);
    return root;
  }
 
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
    return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
    }
};

106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode)

难度中等

给定两个整数数组 inorderpostorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树

示例 1:

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

输出:[3,9,20,null,null,15,7]


示例 2:

输入:inorder = [-1], postorder = [-1]

输出:[-1]


提示:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorderpostorder 都由 不同 的值组成
  • postorder 中每一个值都在 inorder
  • inorder 保证是树的中序遍历
  • postorder 保证是树的后序遍历
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
 
    }
};

解析代码:

class Solution {
public:
  TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& prei, int left, int right)
  {
    if (left > right)
    {
      return nullptr;
    }
    TreeNode* root = new TreeNode(postorder[prei--]); // 从后面开始new
    int ini = left; // 分割中序
    while (ini <= right)
    {
      if (inorder[ini] == root->val)
      {
        break;
      }
      else
      {
        ini++;
      }
    }
    // [left,ini-1] ini [ini+1,right] 先构建右再构建左
    root->right = _buildTree(inorder, postorder, prei, ini + 1, right);
        root->left = _buildTree(inorder, postorder, prei, left, ini - 1);
    return root;
  }
 
  TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    int i = inorder.size() - 1;
    return _buildTree(inorder, postorder, i, 0, inorder.size() - 1);
  }
};

从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(下):https://developer.aliyun.com/article/1521948?spm=a2c6h.13148508.setting.19.50c04f0eHmAr4x

目录
相关文章
|
19小时前
|
C语言 C++
【C++语言】冲突-C语言:命名空间
【C++语言】冲突-C语言:命名空间
|
7天前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
9 1
|
8天前
|
程序员 C语言 C++
C语言学习记录——动态内存习题(经典的笔试题)、C/C++中程序内存区域划分
C语言学习记录——动态内存习题(经典的笔试题)、C/C++中程序内存区域划分
9 0
|
16天前
|
安全 Linux 编译器
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)(下)
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)
22 0
|
16天前
|
安全 C语言 C++
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)(中)
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)
20 0
|
18小时前
|
程序员 C语言 C++
【C++语言】继承:类特性的扩展,重要的类复用!
【C++语言】继承:类特性的扩展,重要的类复用!
|
19小时前
|
C++ 容器 存储
【C++语言】想学STL,先细细拿捏string类,万字详解string类 (内附精美思维导图)
【C++语言】想学STL,先细细拿捏string类,万字详解string类 (内附精美思维导图)
|
19小时前
|
C++ 编译器
【C++语言】Date类的代码实现(操作符重载运用)
【C++语言】Date类的代码实现(操作符重载运用)
|
21小时前
|
C++ 索引
C++ string类常用操作
C++ string类常用操作
|
23小时前
|
编译器 数据安全/隐私保护 C++
c++primer plus 6 读书笔记 第十三章 类继承
c++primer plus 6 读书笔记 第十三章 类继承