用栈中序遍历二叉树

用curr作为额外的栈顶的写法

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode *> stk;
    auto curr = root; // curr是额外栈顶
    while (curr || !stk.empty()) {
        while (curr) { // pushLeft
            stk.push(curr);
            curr = curr->left;
        }
        auto node = stk.top();  stk.pop();
        ans.push_back(node->val);  // 出栈时访问
        curr = node->right;
    }
    return ans;
}
  • https://leetcode.com/problems/binary-search-tree-iterator/
  • https://leetcode.com/problems/recover-binary-search-tree/
  • https://leetcode.com/problems/all-elements-in-two-binary-search-trees/

用栈前序遍历二叉树

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode *> stk;
    auto curr = root; // curr是额外栈顶
    while (curr || !stk.empty()) {
        while (curr) { // pushLeft
            ans.push_back(curr->val); // 进栈前访问
            stk.push(curr);
            curr = curr->left;
        }
        auto node = stk.top(); stk.pop();
        curr = node->right;
    }
    return ans;
}

前序遍历还可用图遍历写法：

vector<int> preorderTraversal(TreeNode* root) {
	// 使用栈的图遍历
	vector<int> ans;
	stack<TreeNode *> stk;
	if (root) stk.push(root);
	while (!stk.empty()) {
		auto node = stk.top(); stk.pop();
		ans.push_back(node->val);
		if (node->right) stk.push(node->right);
		if (node->left) stk.push(node->left);
	}
	return ans;
}

用栈后序遍历二叉树

  • https://leetcode.com/problems/binary-tree-postorder-traversal/

后序遍历要用prev节点来判断是否从右子树返回

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode *> stk;
    auto curr = root; // curr是额外栈顶
    TreeNode *prev = nullptr;
    while (curr || !stk.empty()) {
        while (curr) { // pushLeft
            stk.push(curr);
            curr = curr->left;
        }
        auto node = stk.top();
        if (node->right && prev != node->right) { // 不是从右子树返回，访问右子树
            curr = node->right;
        } else { // 从右子树返回，出栈并访问
            stk.pop();
            ans.push_back(node->val);
            prev = node;
        }
    }
    return ans;
}

有父指针，中序遍历的下个节点

  • 有右儿子：右儿子的最左儿子为下个节点
  • 无右儿子：当前节点是右儿子时不断上移，最终父节点为下个节点 （停下来时父节点为空或当前节点是左儿子）
TreeLinkNode* inorderSucc(TreeLinkNode* node) {
    if (!node) return nullptr;
    if (node->right) {
        auto curr = node->right;
        while (curr->left) {
	        curr = curr->left;
	    }
        return curr;
    }

    while (node->parent && node == node->parent->right) {
        node = node->parent;
    }
    return node->parent;
}
有父指针，中序遍历的上个节点

同样地，

  • 有左儿子：左儿子的最右儿子为下个节点
  • 无左儿子：当前节点是左儿子时不断上移，最终父节点为下个节点

扩展：