二叉树相关OJ - C++

根据二叉树创建字符串

题目链接：leetcode606.根据二叉树创建字符串

题目：

分析：

此题我们可以递归创建字符串，只是递归的时候需要注意什么时候需要加括号或者不加括号。这题的节点数据使用 to_string 函数转换成字符串。

1、节点左右子树都为空时，或者右子树是空树时，括号省略掉。
2、左子树为空，右子树不为空，则括号不能省略。

注意：此题中，我们使用子函数进行递归创建字符串，str使用传引用接收，减少拷贝从而增加效率。

题解：

class Solution {
public:
    // 使用传引用接收，减少拷贝，提高效率
    void _tree2str(TreeNode* root,string& str)
    {
        // 树为空
        if(root==nullptr)
            return;

        // str加上节点数据转出的字符串
        str+=to_string(root->val);

        // 递归左子树创建字符串
        if(root->left) // 左子树不为空
        {
            str+='(';
            _tree2str(root->left,str);
            str+=')';
        }
        else if(root->right) // 左子树为空，但右子树不为空
        {
            str+="()";
        }

        // 递归右子树创建字符串
        if(root->right) // 右子树不为空
        {
            str+='(';
            _tree2str(root->right,str);
            str+=')';
        }
    }

    string tree2str(TreeNode* root) {
        string str;
        _tree2str(root,str);
        return str;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

二叉树的层序遍历

题目链接：leetcode102.二叉树的层序遍历

题目：

分析：
用 levelSize 标记每一层节点的数量，每出一个节点，就将当前所出节点的左右节点尾插到队列中，直到队列为空则二叉树遍历完成。

题解：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vv;
        
        // 若二叉树为空，则返回一个空的匿名对象
        if(root==nullptr)
            return vector<vector<int>>();
           //return vv;

        // 定义一个队列，用来存储二叉树的节点
        queue<TreeNode*> q;
        // 将第一层如队列
        int levelSize=1;
        q.push(root);
        // 队列不为空，则表明二叉树结点没有出完，直到为空则遍历完成
        while(!q.empty())
        {
            // 存储每一层的数据
            vector<int> v;
            while(levelSize--)// 控制当前层的数据出完
            {
                // 取出队头结点，并将其数据尾插到v中
                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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

二叉树的最近公共祖先

题目链接：leetcode236.二叉树的最近公共祖先

题目：

分析：
除了最后一种情况，p和q中本身有一个节点就是最近公共祖先，除此之外，p和q两个节点一定分别在最近公共祖先节点的左右两侧。

题解：

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) 
    {
        // p节点或q节点为当前根节点，则它就是最近公共祖先
        if(q==root||p==root)
            return root;

        // 确定p和q节点在当前节点的左子树还是右子树
        bool pInLeft,qInLeft,qInRight,pInRight;

        // 因为p和q一定在二叉树中，所以p和q节点不是在根节点左边，那么就是在根节点右边
        pInLeft=find(root->left,p);
        pInRight=!pInLeft;

        qInLeft=find(root->left,q);
        qInRight=!qInLeft;

        // p和q节点都在当前根节点左边，则递归左子树继续查找
        if(pInLeft&&qInLeft)
            return lowestCommonAncestor(root->left,p,q);
        // p和q节点都在当前根节点右边，则递归右子树继续查找
        else if(pInRight&&qInRight)
            return lowestCommonAncestor(root->right,p,q);
        // p和q节点在当前节点的左右两侧，则当前节点即是最近公共祖先
        else
            return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

上面的解法在一些特殊的情况下就是比较慢，时间复杂度最坏可达到O(N^2)，因此我们需要对其进行优化处理，如下介绍第二种方法。

1、可将此题转化为链表相交问题，用两个栈分别记录根节点到p和q的路径。
2、让分别记录p和q的栈种长度较大的那个先走差距步。
3、然后一起走，直到找到相同的节点即使他们的最近公共祖先。

递归左右子树，遇到节点就入栈，入当前节点的左右子树均没有目标节点，则该节点出栈，最终栈里面的就是p或q到根节点路径上的节点。

题解：

class Solution {
public:
    bool FindPath(TreeNode* root,TreeNode* x,stack<TreeNode*>& path)
    {
        // 空树，直接返回
        if(root==nullptr)
            return false;

        // 将当前节点入栈，然后与要查找的节点进行对比
        path.push(root);
        if(root==x)
            return true;

        // 若在左子树或者右子树中找到了待查找节点，就返回true
        if(FindPath(root->left,x,path))
            return true;
        if(FindPath(root->right,x,path))
            return true;

        // root不是要找的结点x,左子树和右子树都没有找到，那么root不是x的路径中结点
        path.pop();
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        // 查找p和q的路径，存储在对于的栈中
        stack<TreeNode*> pPath,qPath;
        FindPath(root,p,pPath);
        FindPath(root,q,qPath);

        // 让长的那个栈先走差距步
        while(pPath.size()<qPath.size())
        {
            qPath.pop();
        }
        while(qPath.size()<pPath.size())
        {
            pPath.pop();
        }

        // 两个栈同时走，并取栈顶元素对比，若两个栈栈顶元素相等，则栈顶元素就是最近公共祖先
        while(pPath.top()!=qPath.top())
        {
            pPath.pop();
            qPath.pop();
        }

        // 返回任意一个栈的栈顶元素
        return qPath.top();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

二叉搜索树与双向链表

题目链接： 牛客JZ36.二叉搜索树与双向链表

题目：

分析：
使用中序遍历，定义一个cur指针指向当前中序遍历的结点，prev指向cur的前一个结点，如图所示：第一次cur指向二叉树的最左节点，prev指向空。为了将节点用原有的指针排序成一个双向链表，cur的左指针指向prev，prev的右指针指向cur。

题解：

class Solution {
public:
	// 这里的prev使用传引用接收，让全程只有一个prev，
	// 若用传值接收，则递归时另外一层栈帧中prev的改变不影响上一层
	void InorderConvert(TreeNode* cur,TreeNode*& prev)
	{
		// 当前节点为空，直接返回
		if(cur==nullptr)
			return;
		
		InorderConvert(cur->left, prev);

		// 当前节点的左指针指向前驱节点，若前驱节点不为空，则前驱节点的右指针指向当前节点
		cur->left=prev;
		if(prev)
			prev->right=cur;
		// 向后递归之前，先更新前驱节点
		prev=cur;

		InorderConvert(cur->right, prev);
	}

    TreeNode* Convert(TreeNode* pRootOfTree) {
		// 为空树的情况
        if(pRootOfTree==nullptr)
			return nullptr;

		// 定义一个前驱节点
		TreeNode* prev=nullptr;
		InorderConvert(pRootOfTree,prev);

		// 寻找头节点
		TreeNode* head=pRootOfTree;
		while(head->left)
		{
			head=head->left;
		}
		return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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

题目链接： leetcode105.从前序与中序遍历序列构造二叉树

题目：

分析： 根据前序序列可以确定出二叉树的根，找到根在中序遍历中所处的位置，可确定树的左子树和右子树区间，然后根据前序和中序递归创建二叉树。

题解：

class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder,int& prei,vector<int>& inorder,int inBegin,int inEnd)
    {
        // 区间不符合规范，返回nullptr
        if(inBegin>inEnd)
            return nullptr;

        // 创建根节点
        TreeNode* root=new TreeNode(preorder[prei]);
        ++prei;

        // 划分中序的左右子区间
        int rooti=inBegin;
        while(rooti<=inEnd)
        {
            if(root->val==inorder[rooti])
                break;
            else
                ++rooti;
        }

        // 递归构建左右子树
        // [inBegin,rooti-1] [rooti] [rooti+1,inEnd]
        root->left=_buildTree(preorder,prei,inorder,inBegin,rooti-1);
        root->right=_buildTree(preorder,prei,inorder,rooti+1,inEnd);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int prei=0,inBegin=0,inEnd=inorder.size()-1;
        return _buildTree(preorder,prei,inorder,inBegin,inEnd);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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

题目链接：leetcode106.从中序与后序遍历序列构造二叉树

题目：

分析： 此题和上面一题是类似的，思路相同，只是按照后序来确定根。

题解：

class Solution {
public:
    TreeNode* _buildTree(vector<int>& postorder,int& posti,vector<int>& inorder,int inBegin,int inEnd)
    {
        // 递归区间不符合规范，返回nullptr
        if(inBegin>inEnd)
            return nullptr;

        // 创建根节点
        TreeNode* root=new TreeNode(postorder[posti]);
        --posti;

        // 划分中序遍历中该节点的左右子区间
        int rooti=inBegin;
        while(rooti<=inEnd)
        {
            if(root->val==inorder[rooti])
                break;
            else
                rooti++;
        }

        // 先递归创建右子树，再递归创建左子树
        root->right = _buildTree(postorder,posti,inorder,rooti+1,inEnd);
        root->left = _buildTree(postorder,posti,inorder,inBegin,rooti-1);

        return root;           
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int posti=postorder.size()-1,inBegin=0,inEnd=inorder.size()-1;
        return _buildTree(postorder,posti,inorder,inBegin,inEnd);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

二叉树的前序遍历（非递归）

题目链接：leetcode144.二叉树的前序遍历

题目:

分析：

前序遍历： 根 左子树 右子树

非递归遍历一棵树：

1. 左路节点
2. 左路节点的右子树 – 子问题

题解：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> v;
        TreeNode* cur=root;
        while(!s.empty()||cur) // cur指向哪个节点就表示前序访问这棵树
        {
            // 遍历左路节点，左路节点入栈 -- 访问一棵树的开始
            while(cur)
            {
                v.push_back(cur->val);
                s.push(cur);
                cur=cur->left;
            }

            // 依次去栈中取左路节点的右子树来访问
            TreeNode* top=s.top();
            s.pop();
            // 访问左路节点的右子树 -- 转化为子问题
            cur=top->right;
        }
        return v;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

二叉树的中序遍历（非递归）

题目链接： leetcode94.二叉树的中序遍历

题目：

分析：

中序遍历：左子树 根 右子树

与上题类似，只是根节点的访问需要它的左子树已访问完，因此当前数据在当前节点左子树访问完成之后出栈。

题解：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> v;
        TreeNode* cur=root;

        while(!s.empty()||cur) // cur指向哪个节点就表示前序访问这棵树
        {
            // 左路节点入栈
            while(cur)
            {
                s.push(cur);
                cur=cur->left;
            }

            // 依次取栈中左路节点，这时表示这个节点的左子树已经访问完了，
            // 先访问它，再以子问题的形式去访问它的右子树
            TreeNode* top=s.top();
            s.pop();
            v.push_back(top->val);

            // 子问题的形式去访问这棵右子树
            cur=top->right;
        }
        return v;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

二叉树的后序遍历（非递归）

题目链接：leetcode145.二叉树的后序遍历

题目：

分析：

题解：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode* prev=nullptr;
        TreeNode* cur=root;
        while(!st.empty()||cur)
        {
            // 左路节点保存到栈
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }

            // 取到一个栈顶元素，说明它的左路节点已经访问完了
            // 如果它的右为空，或者右子树已经访问完了（上一个访问的节点是top的右子树），那么就可以访问栈顶元素了
            TreeNode* top=st.top();
            if(top->right==nullptr||top->right==prev)
            {
                v.push_back(top->val);
                prev=top;
                st.pop();
            }
            // top->right!=nullptr,且右子树还没有访问，子问题迭代访问
            else
            {
                cur=top->right;
            }
        }
        return v;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34