二叉树的OJ题——C++

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

题目链接：

606. 根据二叉树创建字符串 - 力扣（LeetCode）

题目描述：

前序遍历二叉树，并且将结果存入到一个string中，并且要使用括号去分割和表示每个节点和子树之间的关系，并且要求省略掉可以省略的括号

解题思路：

根据题意，就是一个二叉树前序递归的问题，对是否省略的问题上分类讨论一下即可

参考代码：

class Solution 
{
public:
    string tree2str(TreeNode* root) 
    {
        if(root == nullptr)
        {
            return "";
        }
        string ret = to_string(root->val);
 
        if(root->left || root->right)
        {
            ret+="(";
            ret+= tree2str(root->left);
            ret+=")";
        }
 
        if(root->right)
        {
            ret+="(";
            ret+=tree2str(root->right);
            ret+=")";
        }
        return ret;
    }
};

二、二叉树的层序遍历

题目链接：

102. 二叉树的层序遍历 - 力扣（LeetCode）

题目描述：

二叉树的层序遍历，就是对二叉树一层一层的进行遍历，题目要求将遍历的结果存在一个二维数组里返回。

解题思路：

利用一个队列，每遍历一个节点，就将该节点的左子树和右子树的根放入队列，每次取队头元素遍历，有种排队进出的感觉，由于需要一层一层的出，因此从第一层开始，就用一个size去记录每一层的个数，通过size去控制每一层出几次，遇到空则不入队列

参考代码：

vectorint>> levelOrder(TreeNode* root) 
    {
        vectorint>> ret;
        queue q;
        int num;
        if(root !=nullptr)
        {
            q.push(root);
        }
        while(!q.empty())
        {
            num = q.size();
            vector<int> tmp;
            while(num--)
            {
                TreeNode* node = q.front();
                if(node->left != nullptr)
                {
                    q.push(node->left);
                    
                }
                if(node->right != nullptr)
                {
                    q.push(node->right);
                } 
                tmp.push_back(node->val);     
                q.pop();
            }
            ret.push_back(tmp);
        }
        return ret;
    }

拓展：

反向层序遍历，要求反向层序遍历，没有特殊要求，则直接将结果逆置即可

107. 二叉树的层序遍历 II - 力扣（LeetCode）

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

题目链接：

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

题目描述：

找两个节点p和q的最近的公共祖先，并且节点本身也能成为祖先，不存在找不到的测试用例

解题思路：

思路一：

通过观察可以发现，当p和q分别在一个节点的左子树和右子树时，这个节点就一定是p和q的最近公共祖先

思路二：

关键在Path如何实现

参考代码：

思路一：

   bool FindNode(TreeNode* root,TreeNode* goal)
    {
        if(root == nullptr)
        {
            return false;
        }
        if(root == goal)
        {
            return true;
        }
        return FindNode(root->left,goal) || FindNode(root->right,goal);
    }
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        if(root == nullptr)
        {
            return nullptr;
        }
        if(root == p)
        {
            return root;
        }
        if(root == q)
        {
            return root;
        }
        bool q_left  = FindNode(root->left,q);
        bool q_right = !q_left;
        bool p_left = FindNode(root->left,p);
        bool p_right = !p_left;
        if((q_left && p_right) || (q_right && p_left))
        {
            return root;
        }
        else if(q_left && p_left)
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        else
        {
            return lowestCommonAncestor(root->right,p,q);
        }     
    }

思路二：

    bool Path(TreeNode* root,TreeNode* goal,stack& st)
    {    
        if(root == nullptr)
        {
            return false;
        }
        st.push(root);
        if(root == goal)
        {
            return true;
        }
        if(Path(root->left,goal,st))
        {
            return true;
        }
        if(Path(root->right,goal,st))
        {
            return true;
        }
        else
        {
            st.pop();
            return false;
        }
 
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        stack st_p;
        stack st_q;
        Path(root,p,st_p);
        Path(root,q,st_q);
 
        while(st_p.size() > st_q.size())
        {
            st_p.pop();
        }
        while(st_p.size() < st_q.size())
        {
            st_q.pop();
        }
        while(st_p.top() != st_q.top())
        {
            st_p.pop();
            st_q.pop();
        }
        return st_p.top();
    }

四、二叉搜索树与双向链表

题目链接：

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

题目描述：

将一颗二叉搜索树转换为一个有序的双向不循环链表，然后返回任意一边的节点，并且要求在原树上进行改造，不允许额外的开空间。

解题思路：

首先，需要有序的遍历二叉搜索树，我们需要使用中序遍历，在中序遍历中，我们需要一边走，一边改变指针的方向，使得前后相互链接，因此我们可以两个指针一起走，同时遍历，记录每一步的前一个节点，并且将他们两个互相链接起来，最后遍历完整棵树，也就改造好了

参考代码：

    void InOrder(TreeNode* root, TreeNode*& prev) {
        if (root == nullptr)
            return;
 
        InOrder(root->left, prev);
        root->left = prev;
        if (prev)
            prev->right = root;
		prev = root;
        InOrder(root->right, prev);
    }
 
    TreeNode* Convert(TreeNode* pRootOfTree) 
	{
		TreeNode* prev = nullptr;
		InOrder(pRootOfTree, prev);
		TreeNode* head = pRootOfTree;
		while(head && head->left)
		{
			head = head->left;
		}
		return head;
    }

五、根据前序与中序遍历序列构造二叉树

题目链接：

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

题目描述：

题目给了一个二叉树前序遍历后的序列和中序遍历后的序列，需要我们根据这两个序列还原构建一个二叉树

解题思路：

首先要知道，如果根据前序和中序序列去还原一颗二叉树，我们需要通过前序序列去确定根，然后在中序序列中找到根的位置，把根位置的两边分别分割成左子树和右子树，然后继续去前序序列中确定子树的根，直到将前序遍历完，也就能够完整分割中序序列，重新构建回一个二叉树

参考代码：

    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int& prei,int inbegin,int inend)
    {
        if(inbegin > inend)
        {
            return nullptr;
        }
 
        int root_val = preorder[prei++];
        TreeNode* root = new TreeNode(root_val);
        //找到在中序序列中根的位置,分割区间
        int rooti = inbegin;
        while(inorder[rooti] != root_val)
        {
            rooti++;
        }
 
        root->left = _buildTree(preorder,inorder,prei,inbegin,rooti-1);
        root->right =_buildTree(preorder,inorder,prei,rooti+1,inend);
        return root;
    }
 
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int prei = 0;
        return _buildTree(preorder,inorder,prei,0,inorder.size()-1);
    }

拓展：

通过中序遍历和后序遍历序列重构二叉树，思路上和这个类似

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

六、非递归_前序遍历

题目链接：

144. 二叉树的前序遍历 - 力扣（LeetCode）

题目描述：

用非递归的方式走前序遍历

解题思路：

我们需要借助一个栈，将问题划分为两步，一是先左边的节点全部入栈，然后再一个个出栈解决每个节点的右子树，每个右子树又得当成子问题一样处理

参考代码：

   vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        stack st;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            while(cur)
            {
                ret.push_back(cur->val);
                st.push(cur);
                cur=cur->left;
            }
            
            TreeNode* top = st.top();
            st.pop();
            cur = top->right;
        }
        return ret;
    }

拓展：

非递归_中序遍历和非递归_后序遍历，思路上一样，后序遍历需要一定的特殊处理

94. 二叉树的中序遍历 - 力扣（LeetCode）

145. 二叉树的后序遍历 - 力扣（LeetCode）

后序遍历的处理，需要对什么时候取节点的值需要进行判断，根据画图分析，将情况分类为两种，一种是栈顶元素的右子树为空时，则输出，并且将该节点pop掉，当右子树不为空时，则需要进一步对右子树的值进行入栈，并且不能将该节点pop，只有在该节点被输出后才可以pop

对节点什么时候输出分两种情况，一种是左子树走完，右子树为空，另一种是左子树走完，右子树也走完，出栈元素一定是走完左子树的，对于右子树需要进一步判断，而需要判断右子树是否走完则需要额外的一个节prev去记录上一次pop的数据，如果上一次pop的数据是该节点的右子树，则说明该节点走完了右子树，需要输出