美文网首页
94.二叉树的中序遍历

94.二叉树的中序遍历

作者: 名字是乱打的 | 来源:发表于2021-10-12 01:15 被阅读0次

    借这个题目延展一下,一次写完前序,后序,中序的递归和非递归写法

    一. 递归解法

    如下所示,只要调整dfs遍历顺序就可以轻松得到先序,中序,后序的遍历结果了;

    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res= new LinkedList<>();
            dfs(res,root);
            return res;
        }
    
        private void dfs(List<Integer> res, TreeNode root) {
            if (root==null){
                return;
            }
            dfs(res,root.left);
            res.add(root.val);
            dfs(res,root.right);
        }
    }
    

    二.非递归解法

    1.先序

    public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> res= new LinkedList<>();
            Stack<TreeNode> stack=new Stack<>();
            if (root==null){
                return res;
            }
            //打印,左,右
            stack.push(root);
    
            while (!stack.isEmpty()){
                TreeNode curr = stack.pop();
                res.add(curr.val);
                //栈先进后出,我们要后面打印右树,因此先把右树放进去
                if (curr.right!=null){
                    stack.push(curr.right);
                }
    
                if (curr.left!=null){
                    stack.push(curr.left);
                }
            }
            return res;
        }
    

    中序

    public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res= new LinkedList<>();
            Stack<TreeNode> stack=new Stack<>();
    
            while (root!=null||stack.size()>0){
                //直到不能继续向左再停止
                if (root!=null){
                    stack.add(root);
                    root=root.left;
                    //如果root为null说明stack最新的一个结点无左节点,
                    // 因此直接先打印本节点,再迭代调用B结点
                }else {
                    TreeNode pop = stack.pop();
                    res.add(pop.val);
                    root=pop.right;
                }
            }
            return res;
        }
    

    后序
    前面俩我都是用的栈方式,后序遍历我也提供一个栈方式;
    后续遍历跟先序遍历比较像,这里是定义了两个栈,把打印的放在打印栈stack2里

    public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res= new LinkedList<>();
            if (root==null){
                return res;
            }
            //先序栈
            Stack<TreeNode> stack1=new Stack<>();
            //打印栈
            Stack<Integer> stack2=new Stack<>();
            stack1.push(root);
            while (!stack1.isEmpty()){
                TreeNode pop = stack1.pop();
                stack2.push(pop.val);
                if (pop.left!=null){
                    stack1.push(pop.left);
                }
    
                if (pop.right!=null){
                    stack1.push(pop.right);
                }
            }
    
            //打印
            while (!stack2.isEmpty()){
                res.add(stack2.pop());
            }
    
            return res;
        }
    

    跟leetcode学到,这里再提供一个高效的,双向链表版本

    {
                LinkedList<Integer> res = new LinkedList<>();
                if (root == null) {
                    return res;
                }
                Stack<TreeNode> stack = new Stack<>();
    
                while (!stack.isEmpty() || root != null) {
                    while (root != null) {
                        res.addFirst(root.val);
                        stack.push(root);
                        root = root.right;
                    }
    
                    if (!stack.isEmpty()) {
                        root = stack.pop();
                        root = root.left;
                    }
                }
                return res;
            }
    
    

    相关文章

      网友评论

          本文标题:94.二叉树的中序遍历

          本文链接:https://www.haomeiwen.com/subject/ictdoltx.html