java中使用多种迭代写法实现二叉树遍历的案例分析

这篇文章主要为大家展示了“java中使用多种迭代写法实现二叉树遍历的案例分析”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“java中使用多种迭代写法实现二叉树遍历的案例分析”这篇文章吧。

思想

利用栈和队列都可以实现树的迭代遍历。递归的写法将这个遍历的过程交给系统的堆栈去实现了，所以思想都是一样的、无非就是插入值的时机不一样。利用栈的先进先出的特点，对于前序遍历、我们可以先将当前的值放进结果集中，表示的是根节点的值、然后将当前的节点加入到栈中、当前的节点等于自己的left、再次循环的时候、也会将left作为新的节点、直到节点为空、也就是走到了树的最左边、然后回退、也就是弹栈、、也可以认为回退的过程是从低向上的、具体就是让当前的节点等于栈弹出的right、继续重复上面的过程，也就实现了树的前序遍历、也就是bfs.后续遍历、中序遍历思想也是类似的。

实现

public List<Integer> preorderTraversal1(Treenode root) {        List<Integer> res = new ArrayList<>();        Stack<TreeNode> stack = new Stack<>();        while (!stack.isEmpty() || root != null) {            while (root != null) {                res.add(root.val);                stack.add(root);                root = root.left;            }            TreeNode cur = stack.pop();            root = cur.right;        }        return res;    }    public List<Integer> preorderTraversal2(TreeNode root) {        List<Integer> res = new ArrayList<>();        Stack<TreeNode> stack = new Stack<>();        while (!stack.isEmpty() || root != null) {            if (root != null) {                res.add(root.val);                stack.add(root);                root = root.left;            } else {                TreeNode cur = stack.pop();                root = cur.right;            }        }        return res;    }    public List<Integer> preorderTraversal3(TreeNode root) {        List<Integer> res = new ArrayList<>();        if (root == null) return res;        Stack<TreeNode> stack = new Stack<>();        stack.push(root);        while (!stack.isEmpty()) {            TreeNode cur = stack.pop();            res.add(cur.val);            if (cur.right != null) {                stack.push(cur.right);            }            if (cur.left != null) {                stack.push(cur.left);            }        }        return res;    }    public List<Integer> preorderTraversal4(TreeNode root) {        List<Integer> res = new ArrayList<>();        if (root == null) {            return res;        }        LinkedList<TreeNode> queue = new LinkedList<>();        queue.add(root);        while (!queue.isEmpty()) {            root = queue.poll();            res.add(root.val);            if (root.right != null) {                queue.addFirst(root.right);            }            if (root.left != null) {                root = root.left;                while (root != null) {                    res.add(root.val);                    if (root.right != null) {                        queue.addFirst(root.right);                    }                    root = root.left;                }            }        }        return res;    }    public List<Integer> inorderTraversal1(TreeNode root) {        List<Integer> res = new ArrayList<>();        Stack<TreeNode> stack = new Stack<>();        while (root != null || !stack.isEmpty()) {            if (root != null) {                stack.add(root);                root = root.left;            } else {                TreeNode cur = stack.pop();                res.add(cur.val);                root = cur.right;            }        }        return res;    }    public List<Integer> inorderTraversal2(TreeNode root) {        List<Integer> res = new ArrayList<>();        Stack<TreeNode> stack = new Stack<>();        while (root != null || !stack.isEmpty()) {            while (root != null) {                stack.add(root);                root = root.left;            }            TreeNode cur = stack.pop();            res.add(cur.val);            root = cur.right;        }        return res;    }    public List<Integer> postorderTraversal1(TreeNode root) {        List<Integer> res = new ArrayList<>();        if (root == null) return res;        Stack<TreeNode> stack = new Stack<>();        stack.push(root);        while (!stack.isEmpty()) {            TreeNode cur = stack.pop();            res.add(cur.val);            if (cur.left != null) {                stack.push(cur.left);            }            if (cur.right != null) {                stack.push(cur.right);            }        }        Collections.reverse(res);        return res;    }    public List<Integer> postorderTraversal2(TreeNode root) {        List<Integer> res = new ArrayList<>();        Stack<TreeNode> stack = new Stack<>();        while (!stack.isEmpty()) {            while (root != null) {                res.add(root.val);                stack.push(root);                root = root.right;            }            TreeNode cur = stack.pop();            root = cur.left;        }        Collections.reverse(res);        return res;    }    public List<List<Integer>> levelOrder(TreeNode root) {        List<List<Integer>> ret = new ArrayList<>();        if(root == null)return ret;        Queue<TreeNode> queue = new LinkedList<>();        queue.offer(root);        while (!queue.isEmpty()){            int size = queue.size();            List<Integer> list = new ArrayList<>();            while(size!=0){                TreeNode cur = queue.poll();                list.add(cur.val);                if(cur.left!=null){                    queue.offer(cur.left);                }                if(cur.right!= null){                    queue.offer(cur.right);                }                size --;            }            ret.add(list);        }        return ret;    }

以上是“java中使用多种迭代写法实现二叉树遍历的案例分析”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注编程网精选频道！