用递归与迭代完成二叉树的三种遍历-蒲公英云

二叉树的前序遍历

题目

前序遍历题目链接

递归代码

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/

递归代码

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` ，返回它的中序遍历。

中序遍历题目链接

//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 ，返回其节点值的 后序遍历 。

后序遍历题目链接

//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;
            }
        }
    }
}