LeetCode——根据二叉树创建字符串与二叉树的最近公共祖先

有礼貌的灰绅士

发布于 2023-04-17 20:15:40

1640

发布于 2023-04-17 20:15:40

文章被收录于专栏：C++与Linux的学习之路

606. 根据二叉树创建字符串

给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。

空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例 1：

输入：root = [1,2,3,4] 输出：“1(2(4))(3)” 解释：初步转化后得到 “1(2(4()())())(3()())” ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。

示例 2：

输入：root = [1,2,3,null,4] 输出：“1(2()(4))(3)” 解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。提示：树中节点的数目范围是 [1, 104] -1000 <= Node.val <= 1000

原题链接：https://leetcode.cn/problems/construct-string-from-binary-tree/

思路：前序遍历，只要在遍历左子树和右子树前后加括号就可以了，但是打印出来的结果是最初的结果，并没有忽略括号，所以在进入左子树的时候要进行判断，如果是左子树不为空，那么打印左子树，右子树的括号忽略；左子树为空，右子树不为空，那么就将右子树的括号也带上，然后打印左子树的值。

代码：

class Solution {
public:
    string tree2str(TreeNode* root) {
        if(root == nullptr)
            return string();
        string arr;//储存结果
        arr += to_string(root->val);//将前序遍历的值放入
        if(root->left)//如果左子树为空久没必要进入左子树了
        {
            arr += '(';
            arr += tree2str(root->left);//记得将返回的arr拿回来
            arr += ')';
        }
        else if(root->right)//如果左子树为空右子树不为空就添加()
        {
            arr += "()";
        }
        if(root->right)//如果右子树不为空就去遍历右子树
        {
            arr += '(';
            arr += tree2str(root->right);
            arr += ')';
        }
        return arr;
    }
};

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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：输入：root = [1,2], p = 1, q = 2 输出：1

提示：

树中节点数目在范围 [2, 105] 内。 -109 <= Node.val <= 109 所有 Node.val 互不相同。 p != q p 和 q 均存在于给定的二叉树中。

原题链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

思路：这道题的思路是找到两个结点的位置，然后从第一个根节点，到这两个结点的位置经过路径所有结点放入栈中。放入栈的过程：

这里要找4，前序遍历，这里发现6结点的左子树和右子树为空，都不是要找的4结点，那么6就pop掉。

7结点也不是，pop掉。

这样就能找到路径上所有的结点了。

然后比较两个栈，谁长谁先出栈，知道两个栈顶的元素相同为止。代码：

class Solution {
public:
    bool traverse(stack<TreeNode*>& arr,TreeNode* root, TreeNode* p)
    {
        if(root == nullptr)//空就返回错
            return false;
        arr.push(root);//先将值入栈
        if(root == p)//找到返回正确
            return true;
        if(traverse(arr,root->left,p))//在左子树找，找到了就不用继续向下走了，直接返回
            return true;
        if(traverse(arr,root->right,p))//在右子树找，找到了就不用继续向下走了，直接返回
            return true;
        arr.pop();//如果左子树和右子树都没有就直接删除这个结点
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*>arr1;//root->p的所有结点
        stack<TreeNode*>arr2;//root->q的所有结点
        traverse(arr1,root,p);
        traverse(arr2,root,q);
        while(arr1.size() != arr2.size())//先让两个栈的长度相同
        {
            int size1 = arr1.size();
            int size2 = arr2.size();
            if(size1 > size2)
            {
                arr1.pop();
            }
            else if(size1 < size2)
            {
                arr2.pop();
            }
        }
        while(arr1.top() != arr2.top())//找最近的共同祖先
        {
            arr1.pop();
            arr2.pop();
        }
        return arr1.top();
    }
};