C++：二叉樹題進(jìn)階（三種非遞歸遍歷、二叉搜索樹OJ題）-創(chuàng)新互聯(lián)

lc 606 根據(jù)二叉樹創(chuàng)建字符串

給你二叉樹的根節(jié)點(diǎn) root ，請你采用前序遍歷的方式，將二叉樹轉(zhuǎn)化為一個由括號和整數(shù)組成的字符串，返回構(gòu)造出的字符串。

網(wǎng)站建設(shè)哪家好，找成都創(chuàng)新互聯(lián)公司！專注于網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、小程序設(shè)計(jì)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了博州免費(fèi)建站歡迎大家使用！

空節(jié)點(diǎn)使用一對空括號對 “()” 表示，轉(zhuǎn)化后需要省略所有不影響字符串與原始二叉樹之間的一對一映射關(guān)系的空括號對。

題目描述：
從根開始，只要是兒子，就加一層（），**父節(jié)點(diǎn)和兒子之間一定要加()**如果2有單獨(dú)的孩子3,4，則是：2(3)(4)，而如果沒有左孩子而有右孩子，則：2()(4)。不加()不能區(qū)分是左孩子還是右孩子。
看圖：是一個dfs的感覺，只要有左孩子或右孩子，都該加()。因?yàn)榫退阒挥杏液⒆?，也要區(qū)分當(dāng)前是右孩子。
請?zhí)砑訄D片描述

分析：
有兩種情況，我們都需要給左邊加：()。當(dāng)左邊有值，需要加一圈()，當(dāng)左邊無值而右邊有值，也需要多加()，不然只加不加()不能辨別是右邊的（）。
所以思路：

若二叉樹不為空，則先根結(jié)點(diǎn)的值放入字符串。
若左子樹不為空，或者左子樹為空但右子樹不為空，則需要將左子樹的值放入字符串。
若右子樹不為空，則需要將右子樹的值放入字符串。

做法一：效率低，因?yàn)閞eturn字符串做拷貝構(gòu)造。

string tree2str(TreeNode* root) {string res = "";
        if (root == nullptr)
            return "";

        // 先把當(dāng)前放入
        res += to_string(root->val);

        // 左不空 或 左為空但右不空 ：都需要放左邊的值或只給左邊加()。這兩個可以放一起
        if (root->left || root->right)
        {res += '(';
            res += tree2str(root->left);
            res += ')';
        }

        // 右不空 右子樹放字符串
        if (root->right)
        {res += '(';
            res += tree2str(root->right);
            res += ')';
        }
        return res;
    }

做法二：
將值放入?yún)?shù)上，就可以不用傳值而不斷讓它變長。注意過程中，別漏加每個節(jié)點(diǎn)上的本身值到字符串。

string tree2str(TreeNode* root) {if (root == nullptr)
            return "";
        string res = "";
        dfs(root, res);
        return res;
    }

    void dfs(TreeNode* root, string& res)
    {if (root == nullptr)
            return;
        // 把當(dāng)前先加上
        res += to_string(root->val);
        // 左樹有或右樹有，都加
        if (root->left || root->right)
        {res += '(';
            dfs(root->left, res);
            res += ')';
        }
        // 右樹存在，就加上右樹值
        if (root->right)
        {res += '(';
            dfs(root->right, res);
            res += ')';
        }
    }

二叉樹的非遞歸遍歷

前序遍歷：
前序遍歷的訪問順序是：根、左、右。
做法：

根節(jié)點(diǎn)和根的左孩子都是在左路節(jié)點(diǎn)上，如下圖所示，我們先挨著根、左孩子一直訪問，這樣把左路節(jié)點(diǎn)都拿到了，再依次拿每個節(jié)點(diǎn)的右子樹上所有節(jié)點(diǎn)。比如：8、3、1，再拿1、3、8的右子樹上所有節(jié)點(diǎn)，這種順序符合棧結(jié)構(gòu)，所以具體做法看2。
具體做法：

創(chuàng)建棧，初始化cur為根，依次拿根和根的左孩子入棧。
依次出棧每個節(jié)點(diǎn)，如果節(jié)點(diǎn)存在右孩子，則更新cur為右孩子。
整體需要一層循環(huán)（循環(huán)a），條件是：cur不為空或棧不為空。cur不為空，則循環(huán)（循環(huán)b while(cur)）著，去把當(dāng)前和左孩子入棧。循環(huán)b如果做完了，說明局部子樹的左路節(jié)點(diǎn)都拿完了，我們需要彈棧首，更新cur，因?yàn)槲覀冃枰L問每個節(jié)點(diǎn)的右子樹。
cur = top->right;
遍歷的值存入vector，我們可以開始就申請一個vector。關(guān)于存vector：在左路節(jié)點(diǎn)遍歷過程中，先序遍歷是優(yōu)先根原則，所以每次遇到一個根，就可以push。對于每個節(jié)點(diǎn)都會經(jīng)過內(nèi)存的循環(huán)，所以都會放到vector中去。
記憶好該解題模板條件：while(cur || !st.empty())。

代碼

class Solution {public:
    vectorpreorderTraversal(TreeNode* root) {vectorv;
        stackst;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {// 左路節(jié)點(diǎn)需要每次一股腦全加進(jìn)來
            while(cur)
            {st.push(cur);
                v.push_back(cur->val);
                cur = cur->left;
            }
            // 當(dāng)前走至最深的左節(jié)點(diǎn)的右路
            // 這里巧妙在每次右路節(jié)點(diǎn)，只能最深的一個右來更新cur
            TreeNode* top = st.top();
            st.pop();
            // cur可能不存在，但st可能還存在，就利用下次循環(huán)。
            cur = top->right;
        }
        return v;
    }
};

中序遍歷
中序遍歷需要先左再根再右，比如下面的樹，8、3、1，在這個過程中，不能先按8、3、1去存，當(dāng)沒有左孩子時(shí)，才可以考慮去存。所以和先序的區(qū)別在于，存vector得在第二層while()之后存值入vector。也就是說：

每次到當(dāng)前節(jié)點(diǎn)沒有左孩子，說明到達(dá)最左端，此時(shí)出棧頂，可以push該值。再轉(zhuǎn)cur至當(dāng)前節(jié)點(diǎn)的右孩子。因?yàn)樽蠛透窃谝宦返?，push當(dāng)前，其實(shí)也相當(dāng)于push了根。
中序其實(shí)是先序的微調(diào)整。

class Solution {public:
	vectorinorderTraversal(TreeNode* root) {stackst;
		vectorv;
		TreeNode* cur = root;
		while (cur || !st.empty())
		{	// 左路節(jié)點(diǎn)入棧
			while (cur)
			{		// 中序和前序的區(qū)別在出棧才能訪問
				st.push(cur);
				cur = cur->left;
			}
			// 當(dāng)左路節(jié)點(diǎn)從棧中出來，表示左路節(jié)點(diǎn)已經(jīng)訪問過了，應(yīng)該訪問根 這個節(jié)點(diǎn)和他的右子樹
			TreeNode* top = st.top();
			st.pop();
			v.push_back(top->val);
			cur = top->right;	// 子問題訪問右子樹
		}
		return v;
	}
};

后序遍歷

如圖，后續(xù)遍歷的訪問順序是左、右、根，所以訪問一個節(jié)點(diǎn)時(shí)遵守的規(guī)則是：左右孩子均無，則訪問，如果有左孩子，則繼續(xù)深入。有右孩子，且訪問過，才能訪問當(dāng)前。
所以這里的做法是：前兩個的模板大體寫法不變，存一個prev記錄上一次訪問的節(jié)點(diǎn)。
步驟：

有左孩子則不斷深入更新cur，且放入棧st中，并更新prev。
出循環(huán)更新cur，直到cur不存在，說明當(dāng)前是局部最左孩子。
然后出棧當(dāng)前節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)如果有右孩子，則說明當(dāng)前節(jié)點(diǎn)節(jié)點(diǎn)是個根，是根就不能訪問，不能存vector。但是還需要判斷，我們是第一次到達(dá)還是第二次到達(dá)這個根，所以判斷：top->right == nullptr或top->right == prev即：頂?shù)挠覟榭栈蝽數(shù)挠以L問過，則可以直接push當(dāng)前值，并更新prev，如果這兩個條件不滿足，說明第一次來，或有右孩子，則更新cur到cur->right。
prev的更新只在push值之后，我們的真正訪問只有在push：val時(shí)，才算真正訪問。

class Solution {public:
	vectorpostorderTraversal(TreeNode* root) {stackst;
		vectorv;
		TreeNode* cur = root;
		TreeNode* prev = nullptr;
		while (cur || !st.empty())
		{	// 左路節(jié)點(diǎn)入棧
			while (cur)
			{		// 中序和前序的區(qū)別在出棧才能訪問
				st.push(cur);
				cur = cur->left;
			}
			// 當(dāng)左路節(jié)點(diǎn)從棧中出來，表示左路節(jié)點(diǎn)已經(jīng)訪問過了，再訪問根這個節(jié)點(diǎn)的右子樹
			// 只要能下到這里來，就說明節(jié)點(diǎn)左孩子都訪問完了，可以訪問右孩子了
			TreeNode* top = st.top();
			// 當(dāng)前節(jié)點(diǎn)沒有右子樹或訪問過了 可以入當(dāng)前節(jié)點(diǎn)
			if (top->right == nullptr || top->right == prev)
			{		v.push_back(top->val);
				// 且可以出棧當(dāng)前
				prev = top;	// 更新prev 說明這個節(jié)點(diǎn)訪問過了
				st.pop();
			}
			else
			{		cur = top->right;
			}
		}
		return v;
	}
};

JZ36. 二叉搜索樹與雙向鏈表

分析：二叉搜索樹變雙向鏈表，需要升序，所以以中序遍歷為模板，之前我們輸出節(jié)點(diǎn)放在inorder(root->left)和inorder(root->right)之間，而現(xiàn)在把輸出節(jié)點(diǎn)變?yōu)樽鲦溄印?/li>
思路：
中序遞歸過程中，我們會最終先到最左節(jié)點(diǎn)，此時(shí)理論為頭節(jié)點(diǎn)，利用傳的參prev使得最左節(jié)點(diǎn)的left為prev，（prev初始為nullptr，正好使第一個節(jié)點(diǎn)前驅(qū)為nullptr）。在中間原本輸出的位置，判斷如果prev存在，則讓prev->right = cur（也就是root），不管prev存在不存在，prev都再需要變?yōu)閏ur。中序繼續(xù)往后走，遞歸去當(dāng)前右子樹。

#includeusing namespace std;

struct TreeNode {int val;
	struct TreeNode* left;
	struct TreeNode* right;
	TreeNode(int x) :
		val(x), left(NULL), right(NULL) {}
}; 

class Solution {public:
    TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode* prev = nullptr;
		inOrder(pRootOfTree, prev);
		TreeNode* head = pRootOfTree;
		while (head->left)
		{	head = head->left;
		}
		return head;
    }

	void inOrder(TreeNode* root, TreeNode* prev)
	{if (root == nullptr)
			return;
		inOrder(root->left, prev);	
		// op
		root->left = prev;
		if (prev)
		{	prev->right = root;
		}
		prev = root;
		inOrder(root->left, prev);
		
	}

};

最近公共祖先

普通二叉樹：leetcode236. 二叉樹的最近公共祖先

思路：尋找從根到兩個節(jié)點(diǎn)的路徑，都放入棧中，棧頂是當(dāng)前節(jié)點(diǎn)，棧底是根。找出兩個棧的高度差，棧深的先出棧差個節(jié)點(diǎn)，再依次比較兩個棧頂，第一個相等的節(jié)點(diǎn)就是最近祖先。

步驟：

find()求路徑函數(shù)：

當(dāng)前為空，返回false，說明走到了空節(jié)點(diǎn)位置還沒找到，就該返回，但是return false，因?yàn)榘l(fā)現(xiàn)找到時(shí)要返回true，停止去別的路徑遞歸。所以空節(jié)點(diǎn)位置是個出口。
當(dāng)前節(jié)點(diǎn)存在，就給棧：path中加入當(dāng)前節(jié)點(diǎn)，如果當(dāng)前值是所尋找，就返回true。
否則繼續(xù)往左邊遞歸，但是加上判斷，如果在左邊遞歸能返回true，這里也返回true，不必往下遞歸去右。
遞歸去右尋找。
如果之前左右都找過，也沒能返回true而終止，說明當(dāng)前節(jié)點(diǎn)不在路徑上。pop()當(dāng)前節(jié)點(diǎn)，再返回false。這里的false，返回后會返回到之前某一有孩子的節(jié)點(diǎn)上，繼續(xù)往別的方向走。

求最近祖先：

找兩個節(jié)點(diǎn)的路徑
看哪個stack_size大，讓大的先出棧差個。
挨個比較棧頂，不等就一直出棧。
停下的時(shí)候必定相等，此時(shí)哪個棧頂都正確。

bool findPath(TreeNode* root, TreeNode* x, stack& path)
    {if(root == nullptr)
            return false;
        path.push(root);    
        if(root->val == x->val)
            return true;
        // 左樹找到，就返回了，不去右樹
        if(findPath(root->left, x, path))
            return true;
        if(findPath(root->right, x, path))
            return true;
        path.pop(); // 節(jié)點(diǎn)左右子樹均沒有，該節(jié)不是路徑上節(jié)點(diǎn)
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {  stackppath, qpath;
              findPath(root, p, ppath);
              findPath(root, q, qpath);
              // 找到了路徑，然后都是倒著的，讓多的先刪掉差個
              
              stacklpath = ppath, spath=qpath;    // 區(qū)分長短路徑
              if(lpath.size()< spath.size())
              {  stackt = lpath;
                  lpath = spath;
                  spath = t;
              }
              int plus = lpath.size() - spath.size();
              while(plus--)
                lpath.pop();
              while(lpath.top()!=spath.top())
              {  lpath.pop();
                  spath.pop();
              }
           return lpath.top();
    }
};

搜索二叉樹：
思路：
尋找p、q，在BST樹中，最近祖先有兩種情況：（特殊情況）其中之一是根，則根是最近公共祖先，因?yàn)閺纳贤略L問。（普通情況）最近公共祖先一定是大于其中之一而小于另外一個。

特殊情況如下：遍歷按從上往下，先根再次根，比如m和n或p和q，都是一個根，而另外一個處于一個根的情況，如果我們訪問到當(dāng)前節(jié)點(diǎn)是p、q中某一個，說明某個節(jié)點(diǎn)處于另外一個節(jié)點(diǎn)的局部根位置。

請?zhí)砑訄D片描述
普通情況下，如0、3的最近祖先1或0、6的最近祖先5，也或者0、4的最近祖先1，都滿足大于其中一個、小于另外一個。

請?zhí)砑訄D片描述
所以步驟如下：

當(dāng)前節(jié)點(diǎn)是p或q中某一個，則當(dāng)前就是答案
當(dāng)前節(jié)點(diǎn)比兩個都小，cur去當(dāng)前的左邊；當(dāng)前節(jié)點(diǎn)比兩個都大，cur去當(dāng)前的右邊。
當(dāng)前節(jié)點(diǎn)比一個大，比另一個小，就是最小公共祖先。

注意

上面過程不會運(yùn)行到某個不存在的節(jié)點(diǎn)，因?yàn)锽ST按上面的規(guī)則不會走到空。
每組情況，都要返回，不管是全大還是全小，都得返回

代碼

class Solution {public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root->val == p->val || root->val == q->val)  // 如果某個節(jié)點(diǎn)是其中之一，其實(shí)比本身值也可以
        {return root;
        }
        // 不會當(dāng)前不存在的節(jié)點(diǎn)上
        if(root->val< p->val && root->val< q->val)
            return lowestCommonAncestor(root->right, p, q);
        else if(root->val >p->val && root->val >q->val)
            return lowestCommonAncestor(root->left, p, q);
        else
            return root;
    }
};

重建二叉樹

思路：
用一個函數(shù)即可，當(dāng)前函數(shù)就行。
去創(chuàng)建樹，參數(shù)是2個vector順序，然后兩個數(shù)組的4個邊界。
在前序中，確定根值，再去中序找根位置，每次創(chuàng)建當(dāng)前節(jié)點(diǎn)，然后再遞歸鏈去左和右，遞歸鏈接左右。

class Solution {public:
	TreeNode* createMyTree(vector& pre, int pleft, int pright, vector& in, int inleft, int inright)
	{//cout<< "pleft = "<< pleft<< " , pright = "<< pright<< " , inleft = "<< inleft<< " , inright = "<< inright<< endl;
		// 出口一定要記好：等于的話，也需要建一個節(jié)點(diǎn) 大于才停止
		if (pleft>pright )
		{	return nullptr;
		}
		
		// 每次根節(jié)點(diǎn)和根節(jié)點(diǎn)的左右邊界
		TreeNode* root = new TreeNode(pre[pleft]);
		// 前序中的第一個是根，根在中序中位置
		int root_Inorder_Index = 0;
		for (int i = inleft; i<= inright; i++)
		{	if (pre[pleft] == in[i])
			{		root_Inorder_Index = i;
				break;
			}
		}
		// 因?yàn)榍懊婢湾e了，沒找到。
		// cout<< "當(dāng)前前序根："<< pre[pleft]<< " , 中序中是："<< in[root_Inorder_Index]<< " , 位置："<< root_Inorder_Index<< endl;
		// 左子樹個數(shù)：
		int Lnums = root_Inorder_Index-inleft;
		// 右子樹個數(shù)：
		//int Rnums = inright - root_Inorder_Index;
		//cout<< "左子樹："<< Lnums<< ", 右子樹："<< Rnums<< endl;
		// 利用左右子樹的數(shù)量，分別拿節(jié)點(diǎn)
		root->left = createMyTree(pre, pleft+1, pleft+Lnums, in, inleft, root_Inorder_Index-1);
		root->right = createMyTree(pre, pleft+Lnums+1, pright, in, root_Inorder_Index+1, inright);
		return root;
	}
	// 遞歸建樹	另用遞歸函數(shù)
	TreeNode* buildTree(vector& preorder, vector& inorder) {if (preorder.size() == 0)
			return nullptr;
		TreeNode* root = createMyTree(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
		return root;
	}
};

中序和后續(xù)遍歷構(gòu)造二叉樹

leetcode 106. 從中序與后序遍歷序列構(gòu)造二叉樹

class Solution {public:
	TreeNode* create(vector& in, int s1, int e1, vector& post, int s2, int e2)
	{if (s1 >e1 || s2 >e2)
			return nullptr;
		TreeNode* root = new TreeNode(post[e2]);
		int rootOfIn = 0;
		for (int i = s1; i<= e1; i++)
		{	if (post[e2] == in[i])
			{		rootOfIn = i;
				break;
			}
		}
		int Lnums = rootOfIn-s1;
		root->left = create(in, s1, rootOfIn-1, post, s2, s2+Lnums-1);
		root->right = create(in, rootOfIn+1, e1, post, s2+Lnums, e2-1);
		return root;
	}


	TreeNode* buildTree(vector& inorder, vector& postorder) {if (inorder.size() == 0)
			return nullptr;
		TreeNode* root = create(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);
		return root;
	}
};

二叉搜索樹與雙向鏈表

錯的

class Solution {public:
	void Inorder(TreeNode* root, TreeNode* prev)
	{// 訪問到空 就返回
		if(root == nullptr)
			return;
		Inorder(root->left, prev);
		// 原本輸出值的地方，我們給它換成做鏈接：一左一右
		root->left = prev;
		if(prev)	// 除了中序第一個節(jié)點(diǎn)時(shí)，prev是null，其它prev都有值
		{	prev->right = root;
		}
		// 只有當(dāng)前節(jié)點(diǎn)的左，全訪問完，才能輪到當(dāng)前做prev，且它是以它為根，右孩子的prev。
		prev = root;
		Inorder(root->right, prev);
	}
    TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == nullptr)
			return nullptr;
		// 按中序遍歷走
		TreeNode* prev = nullptr;
		TreeNode* head = pRootOfTree;
		Inorder(head, prev);
		while(head)
		{	head = head->left;
		}
		return head; 
	}
};

以上錯了，錯在prev在不斷改變，比如cur在14的那個節(jié)點(diǎn)，而prev上一次是10，cur可以通過cur->left遞歸到12，也可以通過cur->right遞歸到16，但是對于cur為14，給12、16傳入的prev是10，我們需要prev每次都做出改變，所以prev用指針的引用，但cur每次會自動隨著遞歸函數(shù)的傳值而變化。

請?zhí)砑訄D片描述

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

名稱欄目：C++：二叉樹題進(jìn)階（三種非遞歸遍歷、二叉搜索樹OJ題）-創(chuàng)新互聯(lián)
網(wǎng)站鏈接：http://bm7419.com/article4/diopoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、建站公司、ChatGPT、網(wǎng)站設(shè)計(jì)、微信小程序、電子商務(wù)

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

C++：二叉樹題進(jìn)階（三種非遞歸遍歷、二叉搜索樹OJ題）-創(chuàng)新互聯(lián)

C++：二叉樹題進(jìn)階（三種非遞歸遍歷、二叉搜索樹OJ題）-創(chuàng)新互聯(lián)