数据结构:二叉树的非递归遍历

144.二叉树的前序遍历

题目描述

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。 提示：

树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100

思路

我们知道前序遍历是按照根–>左子树–>右子树的顺序来遍历的，如果要使用迭代的方法来解决，我们可以使用栈来解决，先把根节点放入栈中，然后将右孩子加入栈，再加入左孩子。因为这样子进栈后，出栈的顺序就是根–>左子树–>右子树

代码

class Solution { 
    public List<Integer> preorderTraversal(TreeNode root) { 
        List<Integer> list=new ArrayList();
        Stack<TreeNode> stack=new Stack();
        if(root==null){ 
            return list;
        }
        //只要栈非空，则把栈顶元素弹出
        stack.push(root);
        while(!stack.isEmpty()){ 
            TreeNode node= stack.pop();
            list.add(node.val);
            if(node.right!=null){ 
                 stack.push(node.right);
            }
            if(node.left!=null){ 
                 stack.push(node.left);
            }
           
           
        }
        return list;

    }
}

题目描述

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

树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100

思路

中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中） 那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

代码

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

后序遍历

题目描述

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。 提示：

树中节点的数目在范围 [0, 100] 内 -100 <= Node.val <= 100

思路

后续遍历的遍历顺序是左右根，前序遍历的遍历顺序是根左右，我们发现我们只需要调整一下左右孩子的进栈顺序，然后再反转一下，就可以得到后序遍历

代码

class Solution { 
    public List<Integer> postorderTraversal(TreeNode root) { 
        List<Integer> list=new ArrayList();
        Stack<TreeNode> stack=new Stack();
        if(root==null){ 
            return list;
        }
        stack.push(root);
        while(!stack.isEmpty()){ 
            TreeNode node=stack.pop();
            list.add(node.val);
            if(node.left!=null){ 
                stack.push(node.left);
            }
            if(node.right!=null){ 
                stack.push(node.right);
            }
        }
    //反转
        Collections.reverse(list);
        return list;


    }
}

层序遍历

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

前提知识

在解决这道题目之前，我们应该先了解什么是层序遍历 层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。 队列先进先出，符合一层一层遍历的逻辑，我们可以使用队列来实现层序遍历

public void levelOrderTraversal(Node root){ 
    if(root==null){ 
        return;
    }
    Queue<Node> queue=new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){ 
        Node node=queue.poll();
        System.out.print(node.val+" ");
        if(node.left!=null) { 
            queue.offer(node.left);
        }
        if(node.right!=null) { 
            queue.offer(node.right);
        }
    }
}

代码

class Solution { 
    public List<List<Integer>> levelOrder(TreeNode root) { 
        if(root==null) { 
            return new ArrayList<List<Integer>>();
        }
        
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //将根节点放入队列中，然后不断遍历队列
        queue.add(root);
        while(queue.size()>0) { 
            //获取当前队列的长度，这个长度相当于 当前这一层的节点个数
            int size = queue.size();
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            //将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
            //如果节点的左/右子树不为空，也放入队列中
            for(int i=0;i<size;++i) { 
                TreeNode t = queue.poll();
                tmp.add(t.val);
                if(t.left!=null) { 
                    queue.offer(t.left);
                }
                if(t.right!=null) { 
                    queue.offer(t.right);
                }
            }
            //将临时list加入最终返回结果中
            res.add(tmp);
        }
        return res;
    }
}