leetcode94：二叉树的中序遍历

题目链接

leetcode

题目描述

给定一个二叉树的根节点 root，返回它的中序遍历 。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

const int NULL_NODE = -101;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i ++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i ++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    递归实现

    时间复杂度：O(n)
        其中 n 是二叉树中的节点数。每个节点恰好被访问一次。
    空间复杂度：O(h)
        其中 h 是二叉树的高度。递归调用的深度最多为树的高度。
        在最坏情况下（树完全不平衡），空间复杂度为 O(n)。
*/
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }

    void dfs(TreeNode* root) {
        if (root == nullptr) return;

        dfs(root->left);
        res.push_back(root->val); // 中序遍历位置
        dfs(root->right);
    }

private:
    vector<int> res;
};

/*
    迭代实现

    使用迭代法写中序遍历，需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

    时间复杂度：O(n)
    空间复杂度：O(h)
*/
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* cur = root;

        while (cur != nullptr || !stk.empty()) {
            // 指针来访问节点，访问到最底层
            if (cur != NULL) {
                stk.push(cur);
                cur = cur->left; // 左
            } else {
                // 从栈里弹出的数据，就是要处理的数据
                cur = stk.top(); stk.pop();
                res.push_back(cur->val); // 中
                cur = cur->right; // 右
            }
        }

        return res;
    }
};

// 思路同上
class Solution_2 {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;

        while (root || stk.size()) {
            while (root) {
                stk.push(root);
                root = root->left;       // 左
            }
            root = stk.top(); stk.pop(); // 中
            res.push_back(root->val);
            root = root->right;          // 右
        }

        return res;
    }
};

/*
    使用栈来模拟递归过程

    栈中每个元素存储两个值：TreeNode 结点和一个整型的标记。
        1.标记 = 0，表示还没遍历该结点的左子树；
        2.标记 = 1，表示已经遍历完左子树，但还没遍历右子树；
        3.标记 = 2，表示已经遍历完右子树。
    根据标记的值，分别处理各种情况：
        1.标记 = 0，将该结点的标记改成 1，然后将其左儿子压入栈中；
        2.标记 = 1，说明左子树已经遍历完，将根结点的值插入答案序列中，
        然后将该结点的标记改成 2，并将右儿子压入栈中；
        3.标记 = 2，说明以该结点为根的子树已经遍历完，直接从栈中弹出。

    时间复杂度：O(n)
        其中 n 为二叉树结点的个数，每个结点仅会遍历一遍，且进栈出栈一次。
    空间复杂度：O(n)。
        取决于递归的栈深度，栈深度在二叉树为一条链的情况下会达到 O(n)。
    
    使用一套机械的方式直接将递归改成非递归，
    效率会低一些，不过通用性比较强。
*/
class Solution_3 {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<pair<TreeNode*, int>> stk;

        // stk.push(make_pair(root, 0));
        stk.push({root, 0});
        while (!stk.empty()) {
            if (stk.top().first == nullptr) {
                stk.pop();
                continue;
            }

            int t = stk.top().second;
            if (t == 0) {
                stk.top().second = 1;
                // stk.push(make_pair(stk.top().first->left, 0));
                stk.push({stk.top().first->left, 0});
            } else if (t == 1) {
                res.push_back(stk.top().first->val);
                stk.top().second = 2;
                // stk.push(make_pair(stk.top().first->right, 0));
                stk.push({stk.top().first->right, 0});
            } else if (t == 2) {
                stk.pop();
            }
        }
        
        return res;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {1, NULL_NODE, 2, 3};

    // 创建二叉树
    TreeNode* root = createTree(nums);

    // 中序遍历
    vector<int> result = solution.inorderTraversal(root);
    // 打印结果
    cout << "Inorder Traversal: ";
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;

    // 释放内存
    deleteTree(root);

    return 0;
}

Golang 代码

package main

import "fmt"

const NULL_NODE = -101

// 定义二叉树节点
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 创建二叉树
func createTree(values []int) *TreeNode {
	if len(values) == 0 {
		return nil
	}
	root := &TreeNode{Val: values[0]}
	queue := []*TreeNode{root}
	i := 1
	for i < len(values) {
		node := queue[0]
		queue = queue[1:]
		if i < len(values) && values[i] != NULL_NODE {
			node.Left = &TreeNode{Val: values[i]}
			queue = append(queue, node.Left)
		}
		i++
		if i < len(values) && values[i] != NULL_NODE {
			node.Right = &TreeNode{Val: values[i]}
			queue = append(queue, node.Right)
		}
		i++
	}
	return root
}

// 打印二叉树（层序遍历）
func printTree(root *TreeNode) string {
	if root == nil {
		return "[]"
	}
	result := []int{}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node == nil {
			result = append(result, NULL_NODE)
			continue
		}
		result = append(result, node.Val)
		queue = append(queue, node.Left)
		queue = append(queue, node.Right)
	}
	// 去掉尾部的 NULL_NODE
	for len(result) > 0 && result[len(result)-1] == NULL_NODE {
		result = result[:len(result)-1]
	}
	return fmt.Sprintf("%v", result)
}

/*
    递归实现

    先递归遍历左子树，
    然后访问当前节点，
    最后递归遍历右子树。
    
    时间复杂度：O(n)
        其中 n 为二叉树节点的个数，二叉树的遍历中每个节点只会被访问一次。
    空间复杂度：O(n)。
        取决于递归的栈深度，栈深度在二叉树为一条链的情况下会达到 O(n)。
*/
func inorderTraversal(root *TreeNode) []int {
    result := []int{}

    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }

        dfs(node.Left)
        result = append(result, node.Val) // 中序遍历位置
        dfs(node.Right)
    }

    dfs(root)
    return result
}

/*
    迭代实现

    使用一个栈，先将当前节点的所有左子节点入栈，
    然后出栈一个节点并访问它，接着处理其右子树。

    时间复杂度：O(n)
        其中 n 为二叉树节点的个数，二叉树的遍历中每个节点只会被访问一次。
    空间复杂度：O(n)。
        取决于递归的栈深度，栈深度在二叉树为一条链的情况下会达到 O(n)。
*/
func inorderTraversal_1(root *TreeNode) []int {
    result := []int{}      // 存储遍历结果
    stack := []*TreeNode{} // 用作栈
    cur := root            // 当前节点初始化为根节点

    for cur != nil || len(stack) > 0 {
        // 遍历左子树
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        // 弹出栈顶节点
        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, cur.Val)
        // 转向右子树
        cur = cur.Right
    }

    return result
}

func main() {
    // 测试用例
    testCases := []struct {
        values   []int
        expected []int
    }{
        {
            values:   []int{1,NULL_NODE,2,3},
            expected: []int{1,3,2},
        },
        {
            values:   []int{},
            expected: []int{},
        },
        {
            values:   []int{1},
            expected: []int{1},
        },
    }

    for i, tc := range testCases {
        root := createTree(tc.values)
        fmt.Printf("Test Case %d, Input: values = %v\n", i+1, printTree(root))
        result := inorderTraversal(root)
        resultStr := fmt.Sprintf("%v", result)
        expectedStr := fmt.Sprintf("%v", tc.expected)

        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
    }
}