leetcode演算法總結 —— 二叉樹前、中、后序遍歷（迭代和遞回兩種解法）

1. 遞回

class Solution {
    public:
	vector<int> preorderTraversal(TreeNode *root)
	{
		vector<int> res;
		dfs(root, res);
		return res;
	}
	//傳參考相當于傳一個全域變數
	void dfs(TreeNode *root, vector<int> &res)
	{
		if (root == nullptr)
			return;
		//前序遍歷
		res.push_back(root->val);
		dfs(root->left, res);
		//中序遍歷
		//res.push_back(root->val);
		dfs(root->right, res);
		//后序遍歷
		//res.push_back(root->val);
	}
};

2. 迭代，易理解解法

時間復雜度為O(n)，因為每個節點只遍歷一次，
空間復雜度最大O(n)，只有當二叉樹成為一條鏈的時候，堆疊需要存盤所有節點，不然堆疊只需要存盤一部分，

前序

   vector<int> preorderTraversal(TreeNode* root) {
       stack<TreeNode*> st;
       vector<int> vRes;
       if (root == NULL) return vRes;
       st.push(root);
       while (!st.empty()) {
		//取堆疊頂元素，也就是中值
           TreeNode* node = st.top();                     
           st.pop();
           vRes.push_back(node->val);
		//如果非空，則右子節點入堆疊，因為是中左右的順序，所以右先入，然后左入
           if (node->right) st.push(node->right);          
           if (node->left) st.push(node->left); 
		//下次先拿左子節點，然后再判斷           
       }
       return vRes;
   }

中序遍歷

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> vRes;
        stack<TreeNode*> st;
        //堆疊中有元素或者當前節點不為空時進行回圈
        //這是模擬遞回的呼叫
        while(st.size() > 0 || root != nullptr) {
            //如果當前節點不為空，則入堆疊并不斷往左子樹方向走
            if(root != nullptr) {
                st.push(root);
                root = root->left;  
            }
            //如果當前節點為空，說明走到頭了
            //從堆疊頂取元素，此時節點為中，并保存
            //然后轉向右邊節點，也就是左中右的順序，繼續上面整個程序
            else {
                TreeNode *tmp = st.top();
                st.pop();
                vRes.push_back(tmp->val);
                root = tmp->right;
            }
        }
        return vRes;
    }

后序遍歷

 vector<int> postorderTraversal(TreeNode *root)
    {
        vector<int> v;
        if (root == nullptr)
            return v;
        stack<TreeNode *> s;
        s.push(root);

        while (!s.empty())
        {
            TreeNode *tempNode = s.top();
            s.pop();
            //先訪問的是根節點
            v.push_back(tempNode->val);

            // 根右左，正好是后續遍歷的倒序
            if (tempNode->left != nullptr)
            {
                s.push(tempNode->left);
            }
            if (tempNode->right != nullptr)
            {
                s.push(tempNode->right);
            }
        }
        //時間復雜度O（n)
        reverse(v.begin(), v.end()); //最后反向一下
        return v;
    }

3. 迭代統一解法

模板

//模擬遞回操作
//模板是根，左，右的順序
while (root != nullptr || !stk.empty()) {
	//如果當前節點非空，一直遍歷到最左子樹
	while (root != nullptr) {
		//根
		stk.push(root);
		//左
		root = root->left;
	}
	//如果root為空也就是左為空，則取出堆疊頂節點，也就是中
	root = stk.top();
	stk.pop();

	//做判斷或者操作
	
	//移動到中的右子節點
	root = root->right;
}

前序遍歷

時間復雜度為O(n)，因為每個節點只遍歷一次，
空間復雜度最大O(n)，只有當二叉樹成為一條鏈的時候，堆疊需要存盤所有節點，不然堆疊只需要存盤一部分，

class Solution {
    public:
	vector<int> preorderTraversal(TreeNode *root)
	{
		vector<int> res;
		stack<TreeNode *> stk;
		while (root != nullptr || !stk.empty()) {
			//一直遍歷到最左子樹
			//因為是前序遍歷，根左右的順序，所以向左走的時候保存
			while (root != nullptr) {
				res.push_back(root->val);
				stk.push(root);
				root = root->left;
			}
			//這時左子樹都入堆疊了
			//如果最左為空，則取中
			//取出堆疊頂節點
			root = stk.top();
			stk.pop();
			//因為中已經保存了，根左右的順序，移動到右子節點
			//最左節點移動到右子樹
			root = root->right;
		}
		return res;
	}
};

中序遍歷

class Solution {
    public:
	//中序遍歷：左中右的順序
	vector<int> inorderTraversal(TreeNode *root)
	{
		vector<int> res;
		stack<TreeNode *> stk;
		while (root != nullptr || !stk.empty()) {
			//一直遍歷到最左子樹
			//因為是中序遍歷，左根右的順序，先不保存
			while (root != nullptr) {
				stk.push(root);
				root = root->left;
			}
			//這時左子樹都入堆疊了
			//如果最左為空，則取中
			//取出堆疊頂節點
			root = stk.top();
			stk.pop();

			//保存
			res.push_back(root->val);
			//移動到中的右子節點
			root = root->right;
		}
		return res;
	}
};

后序遍歷

class Solution {
    public:
	vector<int> postorderTraversal(TreeNode *root)
	{
		vector<int> res;
		stack<TreeNode *> stk;

		TreeNode *prev = nullptr;
		while (root != nullptr || !stk.empty()) {
			//一直遍歷到最左子樹
			//因為是中序遍歷，左右根的順序，先不保存
			while (root != nullptr) {
				stk.push(root);
				root = root->left;
			}
			//這時左子樹都入堆疊了
			//如果最左為空，則取中
			//取出堆疊頂節點
			root = stk.top();
			stk.pop();
			//如果右子樹為慷訓者訪問過
			//則保存當前節點
			//保存當前節點的前一個節點
			if (root->right == nullptr || root->right == prev) {
				res.push_back(root->val);
				prev = root;
				root = nullptr;
			} else {
				//如果不為空并且沒訪問過，則入堆疊，并進入到右子樹
				stk.push(root);
				root = root->right;
			}
		}
		return res;
	}
};