• 笔试题-构建非二叉树，且非递归遍历-利用栈

    普通版本

    package com.fang.恒天软件;


import java.util.*;
import java.util.stream.Stream;


public class Tree {
    TreeNode head;

    public Tree(TreeNode node) {
        this.head = node;
    }


    class ForeachNoMethodException extends Exception {
        public ForeachNoMethodException(String message) {
            super(message);
        }
    }

    private static final String EXCEPTION_MSG = "没有该遍历方式，请从【1(深度优先前序遍历所有)、2(深度优先前序遍历奇数)、3(深度优先前序遍历偶数)、" +
            "4(深度优先后序遍历所有)、5(深度优先后序遍历奇数)、6(深度优先后序遍历偶数)】";

    /**
     * 默认不传走顺序遍历
     */
    public void foreach() {
        foreach(ForEachMethod.orderFrontMethod);
    }



    public void foreach(ForEachMethod method) {
        try {
            if (Stream.of("1", "2", "3").anyMatch(val -> val.equals(method.value))) {
                print(foreachFront(method));;
            } else if (Stream.of("4", "5", "6").anyMatch(val -> val.equals(method.value))) {
                print(foreachBack(method));
            } else {
                throw new ForeachNoMethodException(EXCEPTION_MSG);
            }
        } catch (ForeachNoMethodException ignored) {

        }
    }

    private void print(List<Integer> list) {
        list.forEach(val -> {
            if (list.indexOf(val) == list.size() - 1) {
                System.out.print(val);
            } else {
                System.out.print(val + " ");
            }
        });
    }

    /**
     * 前序遍历
     */
    private List<Integer> foreachFront(ForEachMethod method) {
        List<Integer> result = new ArrayList<>();
        if (Objects.isNull(head)) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            if (Objects.equals(method, ForEachMethod.orderFrontMethod)) {
                result.add(node.value);
            } else if (Objects.equals(method, ForEachMethod.oddFrontMethod) && node.value % 2 != 0) {
                result.add(node.value);
            } else if (Objects.equals(method, ForEachMethod.evenFrontMethod) && node.value % 2 == 0) {
                result.add(node.value);
            }
            for (int i = node.nodes.size() - 1; i >= 0; i--) {
                stack.push(node.nodes.get(i));
            }
        }
        return result;
    }


    /**
     * 后序遍历
     */
    private List<Integer> foreachBack(ForEachMethod method) {
        List<Integer> result = new ArrayList<>();
        if (Objects.isNull(head)) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);

        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (Objects.equals(method, ForEachMethod.orderBackMethod)) {
                result.add(cur.value);
            } else if (Objects.equals(method, ForEachMethod.oddBackMethod) && cur.value % 2 != 0) {
                result.add(cur.value);
            } else if (Objects.equals(method, ForEachMethod.evenBackMethod) && cur.value % 2 == 0) {
                result.add(cur.value);
            }

            for (TreeNode node : cur.nodes) {
                stack.push(node);
            }
        }
        Collections.reverse(result);
        return result;
    }


    /**
     * 非二叉树的节点
     */
    static class TreeNode {
        Integer value;
        List<TreeNode> nodes;

        public TreeNode(Integer value, List<TreeNode> nodes) {
            this.value = value;
            this.nodes = nodes;
        }

        public TreeNode(Integer value) {
            this.value = value;
            this.nodes = new ArrayList<>();
        }
    }

    /**
     * 打印节点方式
     */
    enum ForEachMethod {
        // 根 -> 左 -> 右
        orderFrontMethod("1", "深度优先前序遍历所有"),
        oddFrontMethod("2", "深度优先前序遍历奇数"),
        evenFrontMethod("3", "深度优先前序遍历偶数"),

        // 左 右 根
        orderBackMethod("4", "深度优先后序遍历所有"),
        oddBackMethod("5", "深度优先后序遍历奇数"),
        evenBackMethod("6", "深度优先后序遍历偶数")
        ;

        final String value;
        final String name;

        ForEachMethod(String value, String name) {
            this.value = value;
            this.name = name;
        }
    }

}

class Demo {
    public static void main(String[] args)  {
        List<Tree.TreeNode> treeNodes = new ArrayList<>();

        /**
         *              1
         *           /  |  \
         *        2     3      4
         *      / | \  / \    / \
         *     5  6 7 8   9  10  11
         */
        Tree.TreeNode node5 = new Tree.TreeNode(5);
        Tree.TreeNode node6 = new Tree.TreeNode(6);
        Tree.TreeNode node7 = new Tree.TreeNode(7);
        Tree.TreeNode node2 = new Tree.TreeNode(2, Arrays.asList(node5, node6, node7));

        Tree.TreeNode node8 = new Tree.TreeNode(8);
        Tree.TreeNode node9 = new Tree.TreeNode(9);
        Tree.TreeNode node3 = new Tree.TreeNode(3, Arrays.asList(node8, node9));


        Tree.TreeNode node10 = new Tree.TreeNode(10);
        Tree.TreeNode node11 = new Tree.TreeNode(11);
        Tree.TreeNode node4 = new Tree.TreeNode(4, Arrays.asList(node10, node11));

        Tree.TreeNode head = new Tree.TreeNode(1, Arrays.asList(node2, node3, node4));


        Tree tree = new Tree(head);
        tree.foreach(Tree.ForEachMethod.orderFrontMethod); // 1 2 5 6 7 3 8 9 4 10 11
        System.out.println();
        tree.foreach(Tree.ForEachMethod.oddFrontMethod); // 1 5 7 3 9 11
        System.out.println();
        tree.foreach(Tree.ForEachMethod.evenFrontMethod); // 2 6 8 4 10


        System.out.println("\n-----------------------------------------");
        tree.foreach(Tree.ForEachMethod.orderBackMethod); // 5 6 7 2 8 9 3 10 11 4 1
        System.out.println();
        tree.foreach(Tree.ForEachMethod.oddBackMethod); // 5 7 9 3 11 1
        System.out.println();
        tree.foreach(Tree.ForEachMethod.evenBackMethod); // 6 2 8 10 4
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203

    使用策略模式

    package com.fang.恒天软件;


import java.util.*;




public class Tree {
    TreeNode head;

    public Tree(TreeNode node) {
        this.head = node;
    }


    class ForeachNoMethodException extends Exception {
        public ForeachNoMethodException(String message) {
            super(message);
        }
    }

    private static final String EXCEPTION_MSG = "没有该遍历方式，请从【1(深度优先前序遍历所有)、2(深度优先前序遍历奇数)、3(深度优先前序遍历偶数)、" +
            "4(深度优先后序遍历所有)、5(深度优先后序遍历奇数)、6(深度优先后序遍历偶数)】";

    /**
     * 默认不传走顺序遍历
     */
    public void foreach() {
        foreach(ForEachMethod.orderFrontMethod);
    }

    private void print(List<Integer> list) {
        list.forEach(val -> {
            if (list.indexOf(val) == list.size() - 1) {
                System.out.print(val);
            } else {
                System.out.print(val + " ");
            }
        });
    }



    public void foreach(ForEachMethod method) {
        ForEachFactory factory = new ForEachFactory();
        print(factory.getForEachWay(method).execute());
    }


    class ForEachFactory {
        Map<Tree.ForEachMethod, Tree.ForEachWay> forEachWayMap = new HashMap<>(16, 0.75F);

        public ForEachFactory() {
            registerForEachWay(ForEachMethod.orderFrontMethod, new FrontForEach(ForEachMethod.orderFrontMethod));
            registerForEachWay(ForEachMethod.oddFrontMethod, new FrontForEach(ForEachMethod.oddFrontMethod));
            registerForEachWay(ForEachMethod.evenFrontMethod, new FrontForEach(ForEachMethod.evenFrontMethod));
            registerForEachWay(ForEachMethod.orderBackMethod, new BackForEach(ForEachMethod.orderBackMethod));
            registerForEachWay(ForEachMethod.oddBackMethod, new BackForEach(ForEachMethod.oddBackMethod));
            registerForEachWay(ForEachMethod.evenBackMethod, new BackForEach(ForEachMethod.evenBackMethod));
        }

        private void registerForEachWay(Tree.ForEachMethod method, Tree.ForEachWay way) {
            forEachWayMap.put(method, way);
        }

        public Tree.ForEachWay getForEachWay(ForEachMethod method)  {
            try {
                if (forEachWayMap.containsKey(method)) {
                    return forEachWayMap.get(method);
                } else {
                    throw new ForeachNoMethodException(EXCEPTION_MSG);
                }
            } catch (ForeachNoMethodException e) {

            }
            return null;
        }
    }

    interface ForEachWay {
        List<Integer> execute();
    }

    class FrontForEach implements ForEachWay {

        ForEachMethod method;

        public FrontForEach(ForEachMethod method) {
            this.method = method;
        }

        @Override
        public List<Integer> execute() {
            List<Integer> result = new ArrayList<>();
            if (Objects.isNull(head)) {
                return result;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(head);
            while (!stack.empty()) {
                TreeNode node = stack.pop();
                if (Objects.equals(method, ForEachMethod.orderFrontMethod)) {
                    result.add(node.value);
                } else if (Objects.equals(method, ForEachMethod.oddFrontMethod) && node.value % 2 != 0) {
                    result.add(node.value);
                } else if (Objects.equals(method, ForEachMethod.evenFrontMethod) && node.value % 2 == 0) {
                    result.add(node.value);
                }
                for (int i = node.nodes.size() - 1; i >= 0; i--) {
                    stack.push(node.nodes.get(i));
                }
            }
            return result;
        }
    }




    class BackForEach implements ForEachWay {

        ForEachMethod method;

        public BackForEach(ForEachMethod method) {
            this.method = method;
        }

        @Override
        public List<Integer> execute() {
            List<Integer> result = new ArrayList<>();
            if (Objects.isNull(head)) {
                return result;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(head);

            while (!stack.isEmpty()) {
                TreeNode cur = stack.pop();
                if (Objects.equals(method, ForEachMethod.orderBackMethod)) {
                    result.add(cur.value);
                } else if (Objects.equals(method, ForEachMethod.oddBackMethod) && cur.value % 2 != 0) {
                    result.add(cur.value);
                } else if (Objects.equals(method, ForEachMethod.evenBackMethod) && cur.value % 2 == 0) {
                    result.add(cur.value);
                }

                for (TreeNode node : cur.nodes) {
                    stack.push(node);
                }
            }
            Collections.reverse(result);
            return result;
        }
    }



    /**
     * 非二叉树的节点
     */
    static class TreeNode {
        Integer value;
        List<TreeNode> nodes;

        public TreeNode(Integer value, List<TreeNode> nodes) {
            this.value = value;
            this.nodes = nodes;
        }

        public TreeNode(Integer value) {
            this.value = value;
            this.nodes = new ArrayList<>();
        }
    }

    /**
     * 打印节点方式
     */
    enum ForEachMethod {
        // 根 -> 左 -> 右
        orderFrontMethod("1", "深度优先前序遍历所有"),
        oddFrontMethod("2", "深度优先前序遍历奇数"),
        evenFrontMethod("3", "深度优先前序遍历偶数"),

        // 左 右 根
        orderBackMethod("4", "深度优先后序遍历所有"),
        oddBackMethod("5", "深度优先后序遍历奇数"),
        evenBackMethod("6", "深度优先后序遍历偶数")
        ;

        final String value;
        final String name;

        ForEachMethod(String value, String name) {
            this.value = value;
            this.name = name;
        }
    }

}

class Demo {
    public static void main(String[] args)  {
        List<Tree.TreeNode> treeNodes = new ArrayList<>();

        /**
         *              1
         *           /  |  \
         *        2     3      4
         *      / | \  / \    / \
         *     5  6 7 8   9  10  11
         */
        Tree.TreeNode node5 = new Tree.TreeNode(5);
        Tree.TreeNode node6 = new Tree.TreeNode(6);
        Tree.TreeNode node7 = new Tree.TreeNode(7);
        Tree.TreeNode node2 = new Tree.TreeNode(2, Arrays.asList(node5, node6, node7));

        Tree.TreeNode node8 = new Tree.TreeNode(8);
        Tree.TreeNode node9 = new Tree.TreeNode(9);
        Tree.TreeNode node3 = new Tree.TreeNode(3, Arrays.asList(node8, node9));


        Tree.TreeNode node10 = new Tree.TreeNode(10);
        Tree.TreeNode node11 = new Tree.TreeNode(11);
        Tree.TreeNode node4 = new Tree.TreeNode(4, Arrays.asList(node10, node11));

        Tree.TreeNode head = new Tree.TreeNode(1, Arrays.asList(node2, node3, node4));


        Tree tree = new Tree(head);
        tree.foreach(Tree.ForEachMethod.orderFrontMethod); // 1 2 5 6 7 3 8 9 4 10 11
        System.out.println();
        tree.foreach(Tree.ForEachMethod.oddFrontMethod); // 1 5 7 3 9 11
        System.out.println();
        tree.foreach(Tree.ForEachMethod.evenFrontMethod); // 2 6 8 4 10


        System.out.println("\n-----------------------------------------");
        tree.foreach(Tree.ForEachMethod.orderBackMethod); // 5 6 7 2 8 9 3 10 11 4 1
        System.out.println();
        tree.foreach(Tree.ForEachMethod.oddBackMethod); // 5 7 9 3 11 1
        System.out.println();
        tree.foreach(Tree.ForEachMethod.evenBackMethod); // 6 2 8 10 4
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
  • 相关阅读:
    数据治理体系演进简介
    【图形学】17 光照模型（二、漫反射的Shader实现）
    写爬虫？前端er何必用python
    MongoDB数据库的基本操作
    Gradle系列【5】任务Task
    【MDP】②quadprog求解正定、半正定、负定二次规划
    C++学习笔记一（重载、类）
    【C++】日期类实现，与日期计算相关OJ题
    计算机网络——CSMA/CD协议
    时间、空间复杂度的例题详解
  • 原文地址：https://blog.csdn.net/qq_42582773/article/details/138201915