【LeetCode】二叉树OJ

目录

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

二、二叉树的层序遍历

三、二叉树的层序遍历 II

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

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

六、从前序与中序遍历序列构造二叉树

七、从中序与后序遍历序列构造二叉树

八、二叉树的非递归前序遍历

九、二叉树的非递归中序遍历

十、二叉树的非递归后序遍历

---

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

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

解题思路：本题在递归前序遍历二叉树的同时要注意（）的省略，这时就有了三种情况：

• 如果当前节点没有孩子，我们不需要在节点后面加上任何括号

• 如果当前节点只有左孩子，我们在递归时，只需要在左孩子的结果外加上一层括号，而不需要给右孩子加上任何括号

• 如果当前节点只有右孩子，我们在递归时，需要先加上一层空的括号 ‘()’ 表示左孩子为空，再对右孩子进行递归，并在结果外加上一层括号

解题代码： 

class Solution {
public:
    string tree2str(TreeNode* root) {
        if(root==nullptr)
            return "";
        string str=to_string(root->val);
        if(root->left||root->right)//有左孩子或者无左孩子有右孩子
        {
            str+="(";
            str+=tree2str(root->left);
            str+=")";
        }
       if(root->right)//有右孩子
        {
            str+="(";
            str+=tree2str(root->right);
            str+=")";
        }
        return str;
    }
};

二、二叉树的层序遍历

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

解题思路：本题为了达到层序遍历，我们需要用到一个队列来保存每一层的节点，将将根节点入队列，每次出队列时都要将其孩子节点入队列：

还要有一个变量来记录每一层节点的个数，当该变量不为0时需要将节点出队列，所出节点都属于同一层的元素，每出一个节点将其减1。当该变量为0时，队列中都是上一层节点的孩子节点，所以都属于同一层节点，这时将变量置为队列中元素个数继续将节点出队列即可，直到队列为空

解题代码：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        int levelsize=0;
        if(root)//根节点入队列
        {
            q.push(root);
            levelsize=1;
        }
        vector<vector<int>> vv;
        while(!q.empty())
        {
            vector<int> v;//记录每一层的数据
            while(levelsize--)//将上一层节点出队列的同时，将其孩子节点都入队列
            {
                TreeNode* front=q.front();
                q.pop();
                v.push_back(front->val);
                if(front->left)
                    q.push(front->left);
                if(front->right)
                    q.push(front->right);
            }
            vv.push_back(v);//将遍历完的一层数据存入
            levelsize=q.size();
        }
        return vv;
    }
};

三、二叉树的层序遍历 II

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

解题思路：该题是上题的变形题，很多同学容易在这题中想的过多，这一题想要的结果是上题的结果的逆置，所以按上题思路处理，最后将其结果逆置一下即可：

解题代码：

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> q;
        int levelsize=0;
        if(root)//根节点入队列
        {
            q.push(root);
            levelsize=1;
        }
        vector<vector<int>> vv;
        while(!q.empty())
        {
            vector<int> v;//记录每一层的数据
            while(levelsize--)//将上一层节点出队列的同时，将其孩子节点都入队列
            {
                TreeNode* front=q.front();
                q.pop();
                v.push_back(front->val);
                if(front->left)
                    q.push(front->left);
                if(front->right)
                    q.push(front->right);
            }
            vv.push_back(v);//将遍历完的一层数据存入
            levelsize=q.size();
        }
        reverse(vv.begin(),vv.end());//将结果逆置
        return vv;
    }
};

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

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

解题思路：对于该题我们需要了解两个节点最近公共祖先的特性，即这两个节点分别在最近公共祖先节点的左右子树；所以我们只要找到满足该条件的节点就找到了最近公共祖先节点

解题代码：

class Solution {
public:
    bool IsIntree(TreeNode* root, TreeNode* x)
    {
        if(root==nullptr)
            return false;
        if(root==x)
            return true;
        return IsIntree(root->left,x)||IsIntree(root->right,x);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p||root==q)
            return root;
        bool pInleft=IsIntree(root->left,p);
        bool pInright=!pInleft;
        bool qInleft=IsIntree(root->left,q);
        bool qInright=!qInleft;
        if((pInright&&qInleft)||(pInleft&&qInright))
        {
            return root;
        }
        else if(pInleft&&qInleft)
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        else
        {
            return lowestCommonAncestor(root->right,p,q);
        }
    }
};

但是该方法最坏情况下的时间复杂度为O(N^2)，运行时长并不理想：

那下面我们换个思路来优化一下：我们可以记录从根节点到两个要查找节点的路径，从而将其转换为链表相交问题（对于链表的相交问题我们之前在LeetCode和牛客网经典链表题目合集 讲过），对于路径的存储我们可以用到栈来记录，最终找到共同的最近祖先节点：

class Solution {
public:
    bool GetPath(TreeNode* root, TreeNode* x,stack<TreeNode*>& s)
    {
        if(root==nullptr)
            return false;
        s.push(root);
        if(root==x)
            return true;
        if(GetPath(root->left,x,s)||GetPath(root->right,x,s))
            return true;
        s.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();
    }
};

这样子时间复杂度就降到了O(N)：

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

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

解题思路：在该题中需要利用二叉搜索树中序遍历的结果是升序的，所以我们在中序遍历时修改所在节点与前驱节点的指针指向即可；用cur指针表示当前节点，用prev指针表示中序遍历时当前节点的上一个遍历节点，使cur指针的左孩子：

下面是一个二叉搜索树中序遍历时，修改当前节点和前驱节点的指针指向的演示：

解题代码：

class Solution {
public:
	void InOrder(TreeNode* cur,TreeNode*& prev)
	{
		if(cur==nullptr)
			return;
		InOrder(cur->left,prev);
		cur->left=prev;
		if(prev)
			prev->right=cur;//让前驱节点指针的右孩子指向当前节点
		prev=cur;//更新前驱节点指针位置
		InOrder(cur->right,prev);
	}
    TreeNode* Convert(TreeNode* pRootOfTree) 
	{
		if(pRootOfTree==nullptr)
			return nullptr;
		TreeNode* prev=nullptr;
        InOrder(pRootOfTree,prev);//中序遍历的同时修改二叉树节点指针的指向
		TreeNode* head=pRootOfTree;//pRootOfTree并非链表的头节点，需要找到头节点后返回
		while(head->left)
		{
			head=head->left;
		}
		return head;
    }
};

六、从前序与中序遍历序列构造二叉树

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

解题思路：

对于任意一颗树而言，前序遍历的形式总是

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位

这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置

解题代码：

class Solution {
public:
 
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int begini,int endi,int& n) 
    {
        if(begini>endi)
            return nullptr;
        TreeNode* newnode=new TreeNode(preorder[n]);//先利用先序遍历确定根节点
        int rooti=begini;
        while(rooti<=endi)//找到确定的根节点在中序遍历中的位置
        {
            if(inorder[rooti]==preorder[n])
                break;
            else
                ++rooti;
        }
        ++n;
        newnode->left=_buildTree(preorder,inorder,begini,rooti-1,n);//将剩下的左区间的节点连接到左子树上
        newnode->right=_buildTree(preorder,inorder,rooti+1,endi,n);//将剩下的右区间的节点连接到右子树上
        return newnode;
    }
 
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n=0;
        return _buildTree(preorder,inorder,0,preorder.size()-1,n);
    }
};

七、从中序与后序遍历序列构造二叉树

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

解题思路：该题和上一题是同类型题，我们使用后序遍历的逆序来确定根节点，再在中序遍历中找到其对应的节点，再递归地对构造出右子树和左子树（后序遍历的逆序是相当于先遍历右子树的前序遍历，所以我们先要构建右子树再构建左子树）

解题代码：

class Solution {
public:
    TreeNode* _buildTree(vector<int>& inorder,vector<int>& postorder,int begini,int endi,int& n) 
    {
        if(begini>endi)
            return nullptr;
        TreeNode* newnode=new TreeNode(postorder[n]);//先利用后序遍历确定根节点
        int rooti=begini;
        while(rooti<=endi)//找到确定的根节点在中序遍历中的位置
        {
            if(inorder[rooti]==postorder[n])
                break;
            else
                ++rooti;
        }
        --n;
        newnode->right=_buildTree(inorder,postorder,rooti+1,endi,n);//将剩下的右区间的节点连接到右子树上
        newnode->left=_buildTree(inorder,postorder,begini,rooti-1,n);//将剩下的左区间的节点连接到左子树上
        return newnode;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n=inorder.size()-1;
        return _buildTree(inorder,postorder,0,inorder.size()-1,n);
    }
};

八、二叉树的非递归前序遍历

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

解题思路：这题我们使用递归方法来解决太简单了，下面我们分析一下非递归的思路： 任何一棵二叉树我们都可以将其看成是由左路节点和左路节点的右子树构成的：

我们可以先依次遍历二叉树的左路节点，并将遍历到的节点依次入栈，所有的左路节点遍历完后，再将栈顶元素节点出栈，将其节点右子树转化为左路节点和左路节点的右子树问题来解决

解题代码：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> s;//存储节点的栈
        TreeNode* cur=root;
        while(cur||!s.empty())
        {
            while(cur)
            {
                v.push_back(cur->val);//先将遍历到的左路节点的数据拿出
                s.push(cur);
                cur=cur->left;
            }
            cur=s.top()->right;//将左路节点的右子树的根入栈，转化为子问题
            s.pop();
        }
        return v;
    }
};

九、二叉树的非递归中序遍历

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

解题思路：该题的非递归思路和上一题是一模一样的，无法就是读取节点数据的时机不同，我们需要遍历完节点的左子树才能读取其数据，但是在一个节点出栈时也就代表着其左子树已经全部遍历完了，这时我们就可以读取了

解题代码：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> s;//存储节点的栈
        TreeNode* cur=root;
        while(cur||!s.empty())
        {
            while(cur)
            {
                s.push(cur);
                cur=cur->left;
            }
            v.push_back(s.top()->val);//遍历完所有的左路节点后在将其数据拿出
            cur=s.top()->right;//将左路节点的右子树的根入栈，转化为子问题
            s.pop();
        }
        return v;
    }
};

十、二叉树的非递归后序遍历

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

解题思路：该题我们一样用到将二叉树拆分为左路节点和其右子树的思路，只是在遍历时我们要记录前一个遍历节点的位置（设置一个指针变量prev），这样，在回溯到父节点的时候，我们可以依据prev是指向左子节点，还是右子节点，来判断父节点的右子树是否有被访问过

解题代码：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> s;//存储节点的栈
        TreeNode* cur=root;
        TreeNode* prev=nullptr;
        while(cur||!s.empty())
        {
            while(cur)
            {
                s.push(cur);
                cur=cur->left;
            }
            //已遍历完所有的左路节点
            if(s.top()->right==nullptr||s.top()->right==prev)//该节点无右子树或该节点的右子树已经被遍历过了
            {
                v.push_back(s.top()->val);
                prev=s.top();
                s.pop();
            }
            else
            {
                cur=s.top()->right;//将左路节点的右子树的根入栈，转化为子问题
            }
        }
        return v;
    }
};