一、根据二叉树创建字符串

题目介绍：

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

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

• 树中节点的数目范围是 [1, 104]
• -1000 <= Node.val <= 1000

思路：

这个题就是一个简单的开胃菜，思路就是在前序遍历的过程中先将所有子树都用括号括起来，最后看哪些括号可以省略，观察可以发现，如果左子树不为空，右子树为空，那么右子树括号就可以省略，如果左子树为空，右子树不为空，那左子树的括号不能省略，所以右子树存在就打印括号，不存在就不打印，而左子树存在则一定打印，如果为空的话就要看右子树是否存在

class Solution {
public:
    string tree2str(TreeNode* root) {
        string str;
        if (root == nullptr)
            return str;

        str += to_string(root->val);
        
        if (root->left||(root->left==nullptr&&root->right)) {
            str += '(';
            str+=tree2str(root->left);
            str += ')';
        }

        if (root->right) {
            str += '(';
            str+=tree2str(root->right);
            str += ')';
        }
        return str;
    }
};

二、二叉树的层序遍历

题目介绍：
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

思路1：

对于层序遍历来说很简单，只需要利用一个队列即可，首先将根节点放入队列，在每次出一个节点时，就将这个节点的左右结点放入队列，直到队列为空就遍历完成了，但是这个题目要求我们将每一层的节点数据放到一个数组中，但是我们不知道队列中的每个数据是哪一层的，所以我们可以再创建一个队列，用于记录对应节点的层数

这里就需要两层循环，一层遍历每一层，一层遍历每一层的数据

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vv;
        queue<TreeNode*> q; // 保存结点
        queue<int> qlevel;  // 保存结点的层数
        int level = 1;
        if (root) {
            q.push(root);
            qlevel.push(level);
        }

        while (!q.empty()) {
             vector<int> v;
            while (level == qlevel.front()) {
                   qlevel.pop();
                TreeNode* node = q.front();
                q.pop();
                v.push_back(node->val);

                if (node->left) {
                    q.push(node->left);
                    qlevel.push(level+1);
                }
                if (node->right) {
                    q.push(node->right);
                    qlevel.push(level+1);
                }
            }
            level++;
            vv.push_back(v);
        }
        return vv;
    }
};

思路2：

基于思路1进行优化，我们无非就是需要知道队列中的数据是对应哪一层的，如果我们知道每一层的数据个数，那就很容易控制队列，所以我们就在遍历完一层后，可以根据队列中的数据个数确定下一层的数据个数levelSize，因为上一层的数据都被出去了，而下一层的数据也都被放入队列了。

和上面一样这里也是两层循环

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vv;
        queue<TreeNode*> q;
        int leveSize=0;
        if (root) {
            q.push(root);
            leveSize = 1;
        }
        while (leveSize > 0) {
            vector<int> v;
            while (leveSize--) {
                TreeNode* node = q.front();
                v.push_back(node->val);
                q.pop();

                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            leveSize = q.size();
            vv.push_back(v);
        }
        return vv;
    }
};

补充：

这里还有一个类似的引申题目

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

与上述题目不同的是，他的要求是倒着遍历，那我们可以先正向遍历，最后将结果翻转一下

reverse(vv.begin(), vv.end());

三、二叉树的最近公共祖先

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

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

思路1：

最近公共祖先有两种情况，如果一个节点1在另一个节点2的子树中，那节点2就是公共祖先。如果不是上述的情况，那这两个节点一定一个在公共祖先的左边，一个在右边。

对于一个节点来说，p和q和他的位置关系有三种

• 一个在左一个在右（找到了）
• 都在左（那公共节点一定在左边，往左边找）
• 都在右（那公共节点一定在右边，往右边找）

class Solution {
public:
    bool IsChildTree(TreeNode* root, TreeNode* x) {
        if (root == nullptr)
            return false;

        if (root == x)
            return true;

        return IsChildTree(root->left, x) || IsChildTree(root->right, x);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 发现规律：这两个节点一定一个在最近的公共祖先的左边,一个在右边
        // 或者一个节点是另一个节点的子孙节点
        if (root == nullptr)
            return nullptr;

        if (root == p || root == q)
            return root;

        bool pInLeft,pInRight,qInLeft,qInRight;

        pInLeft=IsChildTree(root->left,p);
        pInRight=!pInLeft;
        qInLeft=IsChildTree(root->left,q);
        qInRight=!qInLeft;
        //一个在左一个在右
        if((pInLeft&&qInRight)||(pInRight&&qInLeft))
        {
            return root;
        }
        else if(pInLeft&&qInLeft)  //都在左边
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        else     //都在右边
        {
            return lowestCommonAncestor(root->right,p,q);
        }
    }
};

但是上面的解法时间复杂度比较高，在最坏的情况下可以到达O(n^2)，因为每次都需要判断两个节点是不是他的子树，如果这个两个节点在靠下的位置，每次判断都需要遍历查找到最下面

思路2：

如果我们有了两个节点到根节点的路径，那么这个题目就可以转变为链表相交的问题

所以重点就到了如何获取一个节点到跟节点的路径，我们可以利用栈，使用前序遍历这个树，碰到一个节点首先把它入栈，因为即使这个节点不是我们要找的节点，这个节点也可能是路径中的一个分支，然后继续遍历他的两个子树，如果他的两个子树都没找到，说明这个节点一定不属于路径中，就把这个节点弹出去。

当获取到两个节点到根节点的路径，首先让长的路径先走，直到两个链表的长度相同，在一块走，直到找到相交点

class Solution {
public:
    bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path) {
        if (root == nullptr)
            return false;

        // 前序遍历的思路，找x结点的路径
        // 遇到root结点先push⼊栈，因为root就算不是x，但是root可能是根->x路径中⼀个分⽀结点             
        path.push(root);
        if (root == x)
            return true;
        if (GetPath(root->left, x, path))
            return true;
        if (GetPath(root->right, x, path))
            return true;

        // 如果左右⼦树都没有x，那么说明上⾯⼊栈的root不是根->x路径中⼀个分⽀结点
        // 所以要pop出栈，回退，继续去其他分⽀路径进⾏查找
        path.pop();

        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath, qPath;
        GetPath(root, p, pPath);
        GetPath(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();
    }
};