Java 二叉树前序遍历（递归/非递归）

一时失言乱红尘 2023-02-13 03:42 114阅读 0赞

### Java 二叉树前序遍历（递归/非递归） ###

*   *  前序遍历
     *  代码实现
     *   *  递归方式
         *  非递归方式

**简介：** 遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。

设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有几种情况：DLR（称为先序遍历），LDR（称为中序遍历），LRD （称为后序遍历），层次遍历。

## 前序遍历 ##

前序遍历：首先访问当前结点，然后递归地访问该结点的左子树，最后递归地访问该结点的右子树。

如图所示二叉树的前序遍历结果为：\[3,9,8,20,15,4,7\]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RyYWN5ZHJhZ29ubHh5_size_16_color_FFFFFF_t_70_pic_center]

## 代码实现 ##

### 递归方式 ###

public List<Integer> preorderTraversal(TreeNode root) {
        
    	List<Integer> pre = new LinkedList<Integer>();
    	preHelper(root,pre);
    	return pre;
    }
    
    public void preHelper(TreeNode root, List<Integer> pre) {
        
    	if(root==null) return;
    	pre.add(root.val);
    	preHelper(root.left,pre);
    	preHelper(root.right,pre);
    }

### 非递归方式 ###

public List<Integer> preorderTraversal(TreeNode root) {
        
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null){
        
            while(cur != null){
        
                list.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
        return list;
    }

完整代码：

public static void main(String[] args) {
        
        TreeNode root = new TreeNode(3);
        TreeNode n1 = new TreeNode(9);
        TreeNode n2 = new TreeNode(20);
        TreeNode n3 = new TreeNode(8);
        TreeNode n4 = new TreeNode(15);
        TreeNode n5 = new TreeNode(7);
        TreeNode n6 = new TreeNode(4);
        root.left = n1;
        root.right = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n4.left = n6;
    
        List<Integer> rs = preorderTraversal(root);
        System.out.println("递归前序遍历结果：" + rs);
    
        rs = preorderTraversal2(root);
        System.out.println("非递归前序遍历结果：" + rs);
    }
    
    // 递归
    public static List<Integer> preorderTraversal(TreeNode root) {
        
        List<Integer> pre = new ArrayList<>();
        preHelper(root,pre);
        return pre;
    }
    
    public static void preHelper(TreeNode root, List<Integer> pre) {
        
        if(root==null) {
        
            return;
        }
        pre.add(root.val);
        preHelper(root.left,pre);
        preHelper(root.right,pre);
    }
    
    // 非递归
    public static List<Integer> preorderTraversal2(TreeNode root) {
        
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null){
        
            while(cur != null){
        
                list.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
        return list;
    }

运行结果：

![在这里插入图片描述][20200709143229293.jpg_pic_left]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RyYWN5ZHJhZ29ubHh5_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200709142156348.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RyYWN5ZHJhZ29ubHh5,size_16,color_FFFFFF,t_70#pic_center
[20200709143229293.jpg_pic_left]: https://img-blog.csdnimg.cn/20200709143229293.jpg#pic_left