二叉树相关题型C++

链接

思路：需要注意的是左右子树的处理，如果左子树为空的话且右子树不为空，要添加一组（）来区分左右子树，如果是右树为空则不用处理

class Solution {
public:
    string tree2str(TreeNode* root) {
        if(root == nullptr)
        return string(); //返回匿名对象

        string str;
        str += to_string(root->val);//用to_string把整数转换为字符
        //1,左不空或左边为空，右边不为空
        if(root->left || root->right)
        {
            str += '(';
            str += tree2str(root->left);
            str += ')';
        }
        //2，右不为空
        if(root->right)
        {
            str += '(';
            str += tree2str(root->right);
            str += ')';
        }
        return str;
    }
};

我们可以注意下这个函数的返回值是string，我们没有用到引用，如果这个树的结构比较大，就会存在大量的string的深拷贝，如何减少深拷贝呢？

我这里的方法是用一个子函数

class Solution {
public:
    string tree2str(TreeNode* root) {
        string str;
        _tree2str(root, str);
        return str;
    }
    void _tree2str(TreeNode* root, string & str) //引用会减少深拷贝
    {
        if(root == nullptr)
        {
            return;
        }
        str += to_string(root->val);
        if(root->left || root->right)
        {
            str += '(';
            _tree2str(root->left,str);
            str += ')';
        }
        if(root->right)
        {
            str += '(';
            _tree2str(root->right, str);
            str += ')';
        }
    }
};

二叉树的层序遍历链接

思路：用一个levelSize记录当层的结点，用队列来存储结点，队列不为空就继续出，每次出levelSize个结点，用这个结点找他的左右不为空的结点入队列

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        if(root == nullptr)
        return vector>();//空树返回匿名对象

        vector> vv;
        queue q;

        int levelSize = 1;//第一个结点数
        q.push(root);
        while(!q.empty())//不为空就继续
        {
            vector v;
            for(int i = 0; i < levelSize; ++i)//没次出levelSize个
            {
                TreeNode* front = q.front();//保存结点
                q.pop();//出掉当前结点
                if(front->left)//左节点不为空入队列
                {
                    q.push(front->left);
                }

                if(front->right)//右节点不为空入队列
                {
                    q.push(front->right);
                }

                v.push_back(front->val);//把当节点的val存起来
            }
            vv.push_back(v);//放到vv里
            levelSize = q.size();//levelSize的大小就是队列的数据个数
        }
        return vv;
    }
};

这题跟上提很像，不过是从下向上遍历，我这边是跟上题一样的思路，然后把VV reverse一下就ok了

class Solution {
public:
    vector> levelOrderBottom(TreeNode* root) {
        if(root == nullptr)
        return vector>();

        vector> vv;
        queue q;

        int levelSize = 1;
        q.push(root);

        while(!q.empty())
        {
            vector v;
            for(int i = 0; i < levelSize; ++i)
            {
                TreeNode* front = q.front();
                q.pop();

                if(front->left)
                {
                    q.push(front->left);
                }
                if(front->right)
                {
                    q.push(front->right);
                }
                v.push_back(front->val);
            }

            levelSize = q.size();
            vv.push_back(v);

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

        return vv;
    }
};

二叉树的最近公共祖先链接

思路：

1.如果是二叉搜索树
从根开始查找
a.如果子节点比根要小，递归到左子树中找
b.如果子节点比根要大，递归到右子树中找
c.如果一个比根小，一个比根大，那么它就是最近的祖先
2. 普通二叉树
从根开始搜索，查找子结点的位置
a.都在左节点，递归到左树去找
b.都在右节点，递归到右树去找
c.如果一个在左，另一个在右，那么它就是最近的共公祖先结点

class Solution {
public:
    bool Find(TreeNode* root, TreeNode* x)
    {
        //走到空说明在这边没有找到
        if(root == nullptr)
        return false;

        //找到了返回真
        if(root == x)
        return true;
        
        //再次递归到左右树找
        return Find(root->left, x) || Find(root->right, x);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        //如果头结点就是其中一个那么他就是
        if(q == root || p == root)
        {
            return root;
        }

        bool ispInLeft, ispInRight, isqInLeft, isqInRight;//判断q,p左树的哪边
        ispInLeft = Find(root->left, p);//去树的左边找p
        ispInRight = !ispInLeft;//取反，没有找到就是在树的右边，找到了就是false

        isqInLeft = Find(root->left, q);
        isqInRight = !isqInLeft;
        
        //1，如果p q，都在树的左边，就递归都树的左边找
        if(ispInLeft && isqInLeft)
        {
            return lowestCommonAncestor(root->left, p, q);
        }
            //2，都在右边
        else if(ispInRight && isqInRight)
        {
            return lowestCommonAncestor(root->right, p, q);
        }
        else//在左右两边,那么根节点就是的
        {
            return root;
        }
    }
};

时间复杂度：
如果最坏的情况：O(n^2),为什么呢？，这题没有说是完全二叉树或者满二叉树，那如果是单支呢？但一般一不会这么坏一般是O(N*logn);

如果要求时间复杂度是O(N)呢？

思路
我们可以找到这个结点所在的路径用栈(其他容器也可以，满足后进先出）保存起来,把两个栈元素个数多的那个先出到相等，然后就是最近的公共祖先

class Solution {
public:

bool FindPath(TreeNode* root, TreeNode* x, stack& path)
{
        if(root == nullptr)
        {
             return false;
        }

        path.push(root);

        if(root == x)
        {
            return true;
        }
        
        if(FindPath(root->left, x, path))
        {
            return true;
        }
        
        if(FindPath(root->right, x, path))
        {
            return true;
        }
            
        path.pop();
        return false;
}
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack pPath, qPath;
        FindPath(root,p, pPath);
        FindPath(root,q, qPath);

        //假设p为结点多的
        stack* longPath = &pPath;
        stack* shortPath = &qPath;
        //判断是不是p比q的结点多
        if(longPath->size() < shortPath->size())
        {
            swap(longPath, shortPath);
        }

        //让长的先走
        while(longPath->size() > shortPath->size())
        {
            longPath->pop();
        }
        while(longPath->top() != shortPath->top())
        {
            longPath->pop();
            shortPath->pop();
        }

        return longPath->top();
    }
};