二叉树相关题目思维难度不高，但是具体快速写出来就需要进行一些模板的记忆了

递归遍历

CPP 递归解法

class Solution { 
   public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        dfs(root, ans);
        return ans;
    }
    void dfs(TreeNode* cur, vector<int>& ans) {
        if (!cur) return;
        ans.push_back(cur->val);
        dfs(cur->left, ans);
        dfs(cur->right, ans); // 这三项交换顺序就是不同的前中后遍历
    }
};

GO 递归解法：

func preorderTraversal(root *TreeNode) (vals []int) {
	var preorder func(*TreeNode)      
    // 因为 preorder 要自己调用自己，所以使用 var 声明然后使用
	preorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		vals = append(vals, node.Val)
		preorder(node.Left)
		preorder(node.Right)
	}
	preorder(root)
	return
}

迭代解法

前序遍历

leetcode-144：二叉树的前序遍历 (opens new window)

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (!root) return ans;
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            ans.push_back(node->val);
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
        return ans;
    }
};

GO version

func preorderTraversal(root *TreeNode) []int {
    ans := []int{}
	if root == nil {
		return ans
	}
	st := list.New()
    st.PushBack(root)
    for st.Len() > 0 {
        node := st.Remove(st.Back()).(*TreeNode)
        ans = append(ans, node.Val)
        if node.Right != nil {
            st.PushBack(node.Right)
        }
        if node.Left != nil {
            st.PushBack(node.Left)
        }
    }
    return ans
}

后序遍历

leetcode-145: 二叉树的后序遍历 (opens new window)

后序遍历就是先获取前序遍历修改左右子树的顺序，然后逆序输出

class Solution {
  public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (!root) return result;
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top(); st.pop();
            ans.push_back(node->val);
            if (node->left) st.push(node->left);    // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
            if (node->right) st.push(node->right);  // 空节点不入栈
        }
        reverse(ans.begin(), ans.end());            
        // 将结果反转之后就是左右中的顺序了
        return ans;
    }
};

GO version

func postorderTraversal(root *TreeNode) []int {
    ans := []int{}
	if root == nil {
		return ans
	}
	st := list.New()
    st.PushBack(root)
    for st.Len() > 0 {
        node := st.Remove(st.Back()).(*TreeNode)
        ans = append(ans, node.Val)
        if node.Left != nil {
            st.PushBack(node.Left)
        }
        if node.Right != nil {
            st.PushBack(node.Right)
        }
    }
    reverse(ans)
    return ans
}
func reverse(a []int) {
    l, r := 0, len(a) - 1
    for l < r {
        a[l], a[r] = a[r], a[l]
        l, r = l+1, r-1
    }
}

中序遍历

leetcode-94: 二叉树的中序遍历 (opens new window)

滑向左链的底端，依次出栈并考虑右侧点

CPP version

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans; 
        if (root == nullptr) return ans; 
        stack<TreeNode*> stk; 
        auto cur = root; 
        while (stk.size() || cur != nullptr) {
            while (cur != nullptr) {
                stk.push(cur); 
                cur = cur->left; 
            }
            cur = stk.top(); 
            stk.pop(); 
            ans.push_back(cur->val); 
            cur = cur->right; 
        }
        return ans; 
    }
}

GO 写法：

因为 list 实现的 stack 不美观，并且速度也没有很大的提升，所以就使用切片了

func inorderTraversal(root *TreeNode) []int {
	ans := make([]int, 0)
	stk := make([]*TreeNode, 0)
	for root != nil || len(stk) > 0 {
		for root != nil {
			stk = append(stk, root)
			root = root.Left
		}
		root = stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		ans = append(ans, root.Val)
		root = root.Right
	}
	return ans
}

层次遍历

lc: 二叉树的层次遍历 (opens new window)

队列：

class Solution {
   public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> que;
        if (root != nullptr) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> item;
            for (int i = 0; i < size; i++) {
                auto node = que.front(); 
                que.pop();
                item.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            ans.push_back(item);
        } 
        return ans;
    }
};

go 中获取 front 元素的写法： node := que.Remove(que.Front()).(*TreeNode)

func levelOrder(root *TreeNode) [][]int {
    ans := [][]int{}
    if root == nil {
        return ans
    }
    que := list.New()
    que.PushBack(root)
    for que.Len() > 0 {
        size := que.Len()
        ansItem := []int{}
        for i := 0; i < size; i++ {
            node := que.Remove(que.Front()).(*TreeNode)
            ansItem = append(ansItem, node.Val)
            if node.Left != nil {
                que.PushBack(node.Left)
            }
            if node.Right != nil {
                que.PushBack(node.Right)
            }
        }
        ans = append(ans, ansItem)
    }
    return ans
}

使用切片：

func levelOrder(root *TreeNode) [][]int {
	ans := [][]int{}
	if root == nil {
		return ans
	}
	que := make([]*TreeNode, 0)
	que = append(que, root)
	for len(que) > 0 {
		size := len(que)
		ansItem := make([]int, 0)
		for i := 0; i < size; i++ {
			node := que[0]
			que = que[1:]
			ansItem = append(ansItem, node.Val)
			if node.Left != nil {
				que = append(que, node.Left)
			}
			if node.Right != nil {
				que = append(que, node.Right)
			}
		}
		ans = append(ans, ansItem)
	}
	return ans
}