算法系列之二叉树中序遍历最佳实践你知道吗

1.概念

二叉树中序遍历算法分为递归遍历和非递归遍历2种实现方式。

递归遍历容易理解，但可能会占用较大的栈空间，需防止出现栈溢出。

2.代码

以下以Java语言代码作为示例。

二叉树的节点的数据结构如下：

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode(int value) {
        this.value = value;
    }
}

1）递归遍历

public void inorderTraversalRecursive(TreeNode root) {
    // 若root节点为空，则子遍历已完成
        if (root == null) {
            return;
        }
    // 遍历左子树
        inorderTraversalRecursive(root.left);
    // 输出遍历到的节点的值
        System.out.print(root.value + " "); 
    // 遍历右子树
        inorderTraversalRecursive(root.right);    
}

2)非递归遍历

public void inorderTraversalNonRecursive(TreeNode root)
{
  // 此栈存储需要后续处理的节点
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    //节点不为空或者栈不为空时需要继续处理
    while(node != null || !stack.empty())
    {
        while(node != null)
        {
      // 1. 保存根节点（方便之后找到并处理右节点）
            stack.push(node);
      // 2. 找到最左节点
            node = node.left;
        }
 
        
        if(!stack.empty())
        {
      // 1. 找到栈顶节点进行处理
            node = stack.pop();
      // 2. 输出遍历到的节点的值
            System.out.println(node.value+" ");
      // 3. 继续处理右子节点
            node = node.right;
        }
    }
}

微风不燥，阳光正好，你就像风一样经过这里，愿你停留的片刻温暖舒心。

我是程序员小迷（致力于C、C++、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等编程技术的技巧经验分享），若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢，您的支持是我们为您提供帮助的最大动力。

欢迎关注。助您在编程路上越走越好！