小米钱包笔试算法2020-12

向右看齐 2022-12-26 11:23 138阅读 0赞

二叉树按层遍历，要求第一层从左往右，第二层从右往左。

import java.util.ArrayList;
    import java.util.List;
    public class test17 {
        public static void main(String[] args) {
            Tree2Node node = new Tree2Node();
            node.value = "3";
            Tree2Node node2 = new Tree2Node();
            node2.value = "9";
            Tree2Node node3 = new Tree2Node();
            node3.value = "20";
            node.leftNode = node2;
            node.rightNode = node3;
            Tree2Node node4 = new Tree2Node();
            node4.value = "15";
            Tree2Node node5 = new Tree2Node();
            node5.value = "7";
            node2.leftNode = node4;
            node2.rightNode = node5;
            System.out.print(node.value);
            System.out.println("");
            Boolean remark = true;
            List<Tree2Node> list = new ArrayList<>();
            list.add(node);
            while( list.size()>0){
                    List newlist = new ArrayList<TreeNode>();
                    if(remark)   {
                        for(int i=list.size()-1;i>=0;i--) {
                            Tree2Node treeNode = list.get(i);
                            if (treeNode.rightNode != null) {
                                System.out.print(treeNode.rightNode.value+" ");
                                newlist.add(treeNode.rightNode);
                            }
                            if (treeNode.leftNode != null) {
                                System.out.print(treeNode.leftNode.value+" ");
                                newlist.add(treeNode.leftNode);
                            }
                            remark = false;
                        }
                    } else{
                        for(int i=0;i<list.size();i++) {
                            Tree2Node treeNode = list.get(i);
                            if (treeNode.leftNode != null) {
                                System.out.print(treeNode.leftNode.value+" ");
                                newlist.add(treeNode.leftNode);
                            }
                            if (treeNode.rightNode != null) {
                                System.out.print(treeNode.rightNode.value+" ");
                                newlist.add(treeNode.rightNode);
                            }
                            remark = true;
                        }
                    }
                System.out.println("");
                list = newlist;
                }
    
            }
        }
    
    class Tree2Node{
        public Tree2Node leftNode;
        public Tree2Node rightNode;
        public String value;
    }

输出结果：

![20201205135410423.png][]

[20201205135410423.png]: /images/20221120/deb65cad51d0479b99c1a068ad946c57.png