美文网首页
二叉树的遍历

二叉树的遍历

作者: 稀饭粥95 | 来源:发表于2018-08-29 11:15 被阅读2次

    从上往下打印二叉树

    从上往下打印出二叉树的每个节点,同层节点从左至右打印。

    public class Solution {
        public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
            if(root==null){
                return new ArrayList<Integer>();
            }
            ArrayList<Integer> list = new ArrayList<Integer>();
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
            }
            return list;
        }
    }
    

    按之字形顺序打印二叉树

    请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

    public class Solution {
        public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
             
            ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
            if(pRoot==null) return results;
            Stack<TreeNode> oddStack = new Stack<TreeNode>();
            Stack<TreeNode> evenStack =new Stack<TreeNode>();
            int flag=0;
            oddStack.push(pRoot);
            while(!oddStack.isEmpty()||!evenStack.isEmpty()){
                ArrayList<Integer> list = new ArrayList<Integer>();
                if(flag%2==0){
                    while(!oddStack.isEmpty()){
                        TreeNode tNode = oddStack.pop();
                        list.add(tNode.val);
                        if(tNode.left!=null) evenStack.push(tNode.left);
                        if(tNode.right!=null) evenStack.push(tNode.right);
                    }
                }else{
                    while(!evenStack.isEmpty()){
                        TreeNode tNode = evenStack.pop();
                        list.add(tNode.val);
                        if(tNode.right!=null) oddStack.push(tNode.right);
                        if(tNode.left!=null) oddStack.push(tNode.left);
                    }
                }
                flag++;
                results.add(list);
            }
            return results;
        }
     
    }
    

    相关文章

      网友评论

          本文标题:二叉树的遍历

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