本文共 3305 字，大约阅读时间需要 11 分钟。

二叉树的前序、中序、后序遍历迭代实现

二叉树的前序遍历，迭代实现 根-左-右 思路： 1、 借用栈的结构 2、 先push(root) 3、 node = pop() 3.1、list.add( node.val ) 3.1、push( node.right ) 3.3、push( node.left ) 4、循环步骤3直到栈空

肯定很难理解，我们一步步执行下，请看图

我们来实现一下代码

public List
   
     preorderTraversal(TreeNode root) {        if (root == null) {            return null;        }        List
    
      list = new ArrayList
     
      ();        Stack
      
        s = new Stack
       
        ();        s.push(root);        while (!s.isEmpty()) {            TreeNode node = s.pop();            list.add(node.val);            if (node.right != null) {                s.push(node.right);            }            if (node.left != null) {                s.push(node.left);            }        }        return list;    }
       
      
     
    
   

中序遍历 左-根-右 思路： 1、 借用栈的结构 2、 把root、以及root左孩子都压入栈中 2.1、node = pop() 2.2、list.add( node.val ) 2.3、root = node.right 3、循环步骤2直到栈为空且root为null

我们实现一下代码

public static List
   
     inorderTraversal(TreeNode root) {        if (root == null) {            return null;        }        List
    
      list = new ArrayList
     
      ();        Stack
      
        s = new Stack
       
        ();        do {            while (root != null) {                s.push(root);                root = root.left;            }            if (!s.isEmpty()) {                TreeNode node = s.pop();                list.add(node.val);                root = node.right;            }        } while (!s.isEmpty() || root != null);        return list;    }
       
      
     
    
   

后序遍历 左-右-根 思路： 1、 借用栈的结构 2、 先push(root) 3、 node = pop() 3.1、list.add( 0 , node.val ) 3.2、push( node.left ) 3.3、push( node.right ) 4、循环步骤3直到栈空

我们实现一下代码

public static List
   
     postorderTraversal(TreeNode root) {        if (root == null) {            return null;        }        List
    
      list = new ArrayList
     
      ();        Stack
      
        s = new Stack
       
        ();        s.push(root);        while( !s.isEmpty() ) {            TreeNode node = s.pop();            if(node.left != null) {                s.push(node.left);            }            if(node.right != null) {                s.push(node.right);            }            list.add(0, node.val);        }        return list;    }
       
      
     
    
   

补充：

TreeNode类class TreeNode {    public int val;    public TreeNode left, right;    public TreeNode(int val) {        this.val = val;        this.left = this.right = null;    }}

前序遍历，递归实现

public void preorderTraversal(TreeNode root) {        if(root != null) {            System.out.print( root.val + " " );            preorderTraversal( root.left );            preorderTraversal( root.right );        }    }

中序遍历，递归实现

public void inorderTraversal(TreeNode root) {        if(root != null) {            inorderTraversal( root.left );            System.out.print( root.val + " " );            inorderTraversal( root.right );        }    }

后序遍历，递归实现

public void postorderTraversal(TreeNode root) {        if(root != null) {            postorderTraversal( root.left );            postorderTraversal( root.right );            System.out.print( root.val + " " );        }    }

递归的实现还是比较简单的，也容易理解； ———————————————— 版权声明：本文为CSDN博主「奇迹码农」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/weixin_42225141/article/details/80572728