用递归与迭代完成二叉树的三种遍历

柔情只为你懂 2023-10-14 21:22 34阅读 0赞

![a1eb6067fb12419da9b9fbccebe7c4cb.jpeg][]

**目录**

二叉树的前序遍历

题目

前序遍历题目链接

递归代码

1.利用方法返回值的代码

2.返回值为void的代码

非递归实现前序遍历(利用栈stack)

1.利用方法返回值的代码

2.返回值为void的代码

二叉树的中序遍历

题目

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

中序遍历题目链接

递归代码

1.利用方法返回值的代码

2.返回值为void的代码

非递归实现中序遍历(利用栈stack)

1.利用方法返回值的代码

2.返回值为void的代码

二叉树的后序遍历

题目

后序遍历题目链接

递归代码

1.利用方法返回值的代码

2.返回值为void的代码

非递归实现中序遍历(利用栈stack)

1.利用方法返回值的代码

2.返回值为void的代码

完结撒花✿✿ヽ(°▽°)ノ✿✿

--------------------

> 遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。  
> 中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。  
> 后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点

## **二叉树的前序遍历** ##

### **题目** ###

:给你二叉树的根节点 `root` ，返回它节点值的 **前序**遍历

### 前序遍历题目链接 ###

: [https://leetcode.cn/problems/binary-tree-preorder-traversal/][https_leetcode.cn_problems_binary-tree-preorder-traversal]

### **递归代码** ###

#### 1.利用方法返回值的**代码** ####

class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> ret = new ArrayList<Integer>();
            if(root==null){
                return ret;
            }
            ret.add(root.val);
            List<Integer> leftTree=preorderTraversal(root.left);
            ret.addAll(leftTree);
            List<Integer> rightTree=preorderTraversal(root.right);
            ret.addAll(rightTree);
            return ret;
            }
    }

#### 2.返回值为void的**代码** ####

// 前序遍历  根  左子树  右子树
        public void preOrder(BTNode root) {
            if (root == null) {
                return;
            }
            System.out.print(root.value + " ");
            preOrder(root.left);
            preOrder(root.right);
        }

### **非递归实现前序遍历(利用栈stack)**  ###

#### 1.利用方法返回值的**代码** ####

class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> ret = new ArrayList<>();
            if (root == null) {
                return ret;
            }
            TreeNode cur = root;
            Deque<TreeNode> stack = new ArrayDeque<>();
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                  //System.out.print(cur.val + " ");
                    ret.add(cur.val);
                    cur = cur.left;
                }
                TreeNode top = stack.pop();
                cur = top.right;
            }
            return ret;
        }
    }

#### 2.返回值为void的**代码** ####

class Solution { 
        public void preOrderNor(BTNode root) {
            if (root == null) {
                return;
            }
            BTNode cur = root;
            Deque<BTNode> stack = new ArrayDeque<>();
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    System.out.println(cur.value + " ");
                    cur = cur.left;
                }
                BTNode top = stack.pop();
                cur = top.right;
            }
        }
    }

--------------------

## 二叉树的中序遍历 ##

### 题目 ###

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

### 中序遍历题目链接 ###

:[https://leetcode.cn/problems/binary-tree-inorder-traversal/][https_leetcode.cn_problems_binary-tree-inorder-traversal]

#### **递归代码** ####

#### 1.利用方法返回值的**代码** ####

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> ret = new ArrayList<>();
            if (root == null) {
                return ret;
            }
            List<Integer> leftTree = inorderTraversal(root.left);
            ret.addAll(leftTree);
            ret.add(root.val);
            List<Integer> rightTree =inorderTraversal(root.right);
            ret.addAll(rightTree);
            return ret;
        }
    }

#### 2.返回值为void的代码 ####

// 中序遍历  左子树  根  右子树
        public void inOrder(BTNode root) {
            if (root == null) {
                return;
            }
            inOrder(root.left);
            System.out.print(root.value + " ");
            inOrder(root.right);
        }

### **非递归实现中序遍历(利用栈stack)**  ###

#### 1.利用方法返回值的**代码** ####

class Solution{
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> ret = new ArrayList<>();
            if (root == null) {
                return ret;
            }
            TreeNode cur = root;
            Deque<TreeNode> stack = new ArrayDeque<>();
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                TreeNode top = stack.pop();
                ret.add(top.val);
                cur = top.right;
            }
            return ret;
        }
    }

#### 2.返回值为void的代码 ####

class Solution{    
        public void inOrderNor(BTNode root) {
            if (root == null) {
                return;
            }
            BTNode cur = root;
            Deque<BTNode> stack = new ArrayDeque<>();
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                BTNode top = stack.pop();
                System.out.println(top.value + " ");
                cur = top.right;
            }
        }
    }

--------------------

## 二叉树的后序遍历 ##

### 题目 ###

:给你一棵二叉树的根节点 `root` ，返回其节点值的 **后序遍历** 。

### 后序遍历题目链接 ###

:[https://leetcode.cn/problems/binary-tree-postorder-traversal/][https_leetcode.cn_problems_binary-tree-postorder-traversal]

#### **递归代码** ####

#### 1.利用方法返回值的代码 ####

class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> ret = new ArrayList<Integer>();
            if(root==null){
                return ret;
            }
            List<Integer> leftTree = postorderTraversal(root.left);
            ret.addAll(leftTree);
            List<Integer> rightTree = postorderTraversal(root.right);
            ret.addAll(rightTree);
            ret.add(root.val);
            return ret;
         }
    }

#### 2.返回值为void的代码 ####

// 后序遍历
        public void postOrder(BTNode root) {
            if (root == null) {
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.value + " ");
        }

### **非递归实现中序遍历(利用栈stack)**  ###

#### 1.利用方法返回值的**代码** ####

class Solution{
         public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> ret = new ArrayList<>();
            if (root == null) {
                return ret;
            }
            TreeNode cur = root;
            TreeNode prev = null;
            Deque<TreeNode> stack = new ArrayDeque<>();
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                TreeNode top = stack.peek();
                if (top.right == null || top.right == prev) {
                    //System.out.println(top.value + " ");
                    ret.add(top.val);
                    stack.pop();
                    prev = top;
                } else {
                    cur = top.right;
                }
            }
            return ret;
        }
    }

#### 2.返回值为void的代码 ####

class Solution{  
        public void postOrderNor(BTNode root) {
            if (root == null) {
                return;
            }
            BTNode cur = root;
            BTNode prev = null;
            Deque<BTNode> stack = new ArrayDeque<>();
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                BTNode top = stack.peek();
                if (top.right == null || top.right == prev) {
                    System.out.println(top.value + " ");
                    stack.pop();
                    prev = top;
                } else {
                    cur = top.right;
                }
            }
        }
    }

## 完结撒花✿✿ヽ(°▽°)ノ✿✿ ##

![410feca848b54f7a90797406962248b6.gif][]

[a1eb6067fb12419da9b9fbccebe7c4cb.jpeg]: https://img-blog.csdnimg.cn/a1eb6067fb12419da9b9fbccebe7c4cb.jpeg
[https_leetcode.cn_problems_binary-tree-preorder-traversal]: https://leetcode.cn/problems/binary-tree-preorder-traversal/
[https_leetcode.cn_problems_binary-tree-inorder-traversal]: https://leetcode.cn/problems/binary-tree-inorder-traversal/
[https_leetcode.cn_problems_binary-tree-postorder-traversal]: https://leetcode.cn/problems/binary-tree-postorder-traversal/
[410feca848b54f7a90797406962248b6.gif]: https://img-blog.csdnimg.cn/410feca848b54f7a90797406962248b6.gif