首页 > 其他分享 >[左神面试指南] 二叉树[上]篇

[左神面试指南] 二叉树[上]篇

时间：2023-11-10 20:24:38浏览次数：41  
标签：right TreeNode int 左神 面试 edges 二叉树 root public

CDXXX 用递归和非递归方式实现二叉树先序、中序和后序遍历❗

public class CDbianli_1
{
    public static class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int num)
        {
            this.val = num;
        }

        public static TreeNode createTree()
        {
            TreeNode[] nodes = new TreeNode[10];
            for (int i = 0; i < nodes.length; i++)
                nodes[i] = new TreeNode(i);
            nodes[1].left = nodes[2];
            nodes[1].right = nodes[3];
            nodes[2].left = nodes[4];
            nodes[2].right = nodes[5];
            nodes[3].right = nodes[6];
            return nodes[1];
        }

    }

    public static void solutionPre(TreeNode root)
    {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty())
        {
            TreeNode popNode = stack.pop();
            System.out.print(popNode.val + " ");
            if (popNode.right != null)
                stack.add(popNode.right);
            if (popNode.left != null)
                stack.add(popNode.left);
        }
        System.out.println();
    }

    public static void solutionIn(TreeNode root)
    {
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null)
        {
            if (root != null)
            {
                stack.add(root);
                root = root.left;
            }
            else
            {
                root = stack.pop();
                System.out.print(root.val + " ");
                root = root.right;
            }
        }
        System.out.println();
    }

    public static void solutionPos1(TreeNode root)
    {
        if (root == null) return;
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(root);
        while (!s1.isEmpty())
        {
            root = s1.pop();
            s2.push(root);
            if (root.left != null)
                s1.push(root.left);
            if (root.right != null)
                s1.push(root.right);
        }
        while (!s2.isEmpty())
            System.out.print(s2.pop().val + " ");
        System.out.println();
    }

    public static void solutionPos2(TreeNode root)
    {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode c = null;
        while (!stack.isEmpty())
        {
            c = stack.peek();
            if (c.left != null && root != c.left && root != c.right)
                stack.push(c.left);
            else if (c.right != null && root != c.right)
                stack.push(c.right);
            else
            {
                System.out.print(stack.pop().val + " ");
                root = c;
            }
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        TreeNode root = TreeNode.createTree();
        solutionPre(root);
        solutionIn(root);
        solutionPos1(root);
        solutionPos2(root);
    }
}

CD162 打印二叉树的边界节点⭐

/*
 * ⭐递归⭐
 * 1. 每层的左右节点 + 叶子节点
 * 2. 左边延长线+ 右边延长线 + 叶子节点
 */
public class CD162_1
{
    public static class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int num)
        {
            this.val = num;
        }

        public static TreeNode createTree(int[][] edges, int root)
        {
            TreeNode[] treeNodes = new TreeNode[edges.length + 1];
            Arrays.setAll(treeNodes, TreeNode::new);
            for (int i = 0; i < edges.length; i++)
            {
                if (edges[i][1] != 0)
                    treeNodes[edges[i][0]].left = treeNodes[edges[i][1]];
                if (edges[i][2] != 0)
                    treeNodes[edges[i][0]].right = treeNodes[edges[i][2]];
            }
            return treeNodes[root];
        }
    }

    public static ArrayList<Integer> solution1(TreeNode root)
    {
        ArrayList<Integer> ans = new ArrayList<>();
        ArrayList<TreeNode[]> levels = new ArrayList<>();
        preOrder(root, levels, 0);
        for (int i = 0; i < levels.size(); i++)
            ans.add(levels.get(i)[0].val);
        findLeaf(root, ans, levels, 0);
        for (int i = levels.size() - 1; i >= 0; i--)
            if (levels.get(i)[1] != levels.get(i)[0])
                ans.add(levels.get(i)[1].val);
        return ans;
    }

    public static void findLeaf(TreeNode root, ArrayList<Integer> ans, ArrayList<TreeNode[]> levels, int depth)
    {
        if (root == null) return;
        if (root.left == null && root.right == null && root != levels.get(depth)[0] && root != levels.get(depth)[1]) ans.add(root.val);
        findLeaf(root.left, ans, levels, depth + 1);
        findLeaf(root.right, ans, levels, depth + 1);
    }

    public static void preOrder(TreeNode root, ArrayList<TreeNode[]> levels, int depth)
    {
        if (root == null) return;
        if (depth + 1 > levels.size()) levels.add(new TreeNode[]{null, null});
        levels.get(depth)[0] = (levels.get(depth)[0] == null ? root : levels.get(depth)[0]);
        levels.get(depth)[1] = root;
        preOrder(root.left, levels, depth + 1);
        preOrder(root.right, levels, depth + 1);
    }

    public static ArrayList<Integer> solution2(TreeNode head)
    {
        if (head == null) return null;
        ArrayList<Integer> ans = new ArrayList<>();
        ans.add(head.val);
        while (true)
        {
            if (head.left == null) head = head.right;
            else if (head.right == null) head = head.left;
            else
            {
                printLeftEdge(head.left, true, ans);
                printRightEdge(head.right, true, ans);
                break;
            }
        }
        return ans;
    }

    public static void printLeftEdge(TreeNode h, boolean print, ArrayList<Integer> ans)
    {
        if (h == null) return;
        if (print || (h.left == null && h.right == null))
            ans.add(h.val);
        printLeftEdge(h.left, print, ans);
        printLeftEdge(h.right, print && h.left == null, ans);
    }

    public static void printRightEdge(TreeNode h, boolean print, ArrayList<Integer> ans)
    {
        if (h == null) return;
        printRightEdge(h.left, print && h.right == null, ans);
        printRightEdge(h.right, print, ans);
        if (print || (h.left == null && h.right == null))
            ans.add(h.val);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, root;
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges = new int[N][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                edges[i][j] = in.nextInt();
        TreeNode rootNode = TreeNode.createTree(edges, root);
        ArrayList<Integer> res = solution1(rootNode);
        System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(" ")));
        res = solution2(rootNode);
        System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }
}

CDXXX 如何较为直观地打印二叉树

略

CD163 二叉树的序列化和反序列化

/* 模拟 */
public class CD163_1
{
    public static class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int num)
        {
            this.val = num;
        }

        public static TreeNode createTree(int[][] edges, int root)
        {
            TreeNode[] treeNodes = new TreeNode[edges.length + 1];
            Arrays.setAll(treeNodes, TreeNode::new);
            for (int i = 0; i < edges.length; i++)
            {
                if (edges[i][1] != 0)
                    treeNodes[edges[i][0]].left = treeNodes[edges[i][1]];
                if (edges[i][2] != 0)
                    treeNodes[edges[i][0]].right = treeNodes[edges[i][2]];
            }
            return treeNodes[root];
        }
    }

    public static String solutionEncodePre(TreeNode root)
    {
        if (root == null) return "#!";
        String ans = root.val + "!";
        String left = solutionEncodePre(root.left);
        String right = solutionEncodePre(root.right);
        return ans + left + right;
    }

    public static TreeNode solutionDecodePre(String str)
    {
        String[] words = str.split("!");
        Queue<String> que = new LinkedList<>();
        Collections.addAll(que, words);
        return createDecodePre(que);
    }

    public static TreeNode createDecodePre(Queue<String> que)
    {
        String pollNode = que.poll();
        if ("#".equals(pollNode)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(pollNode));
        root.left = createDecodePre(que);
        root.right = createDecodePre(que);
        return root;
    }

    public static TreeNode solutionDecodeLevel(String str)
    {
        Queue<TreeNode> que = new LinkedList<>();
        String[] words = str.split("!");
        int idx = 0;
        if ("#".equals(words[idx])) return null;
        TreeNode root = new TreeNode(Integer.parseInt(words[idx]));
        que.add(root);
        idx++;
        while (!que.isEmpty())
        {
            TreeNode pollNode = que.poll();
            if ("#".equals(words[idx]))
                pollNode.left = null;
            else
            {
                pollNode.left = new TreeNode(Integer.parseInt(words[idx]));
                que.add(pollNode.left);
            }
            idx++;
            if ("#".equals(words[idx]))
                pollNode.right = null;
            else
            {
                pollNode.right = new TreeNode(Integer.parseInt(words[idx]));
                que.add(pollNode.right);
            }
            idx++;
        }
        return root;
    }

    public static String solutionEncodeLevel(TreeNode root)
    {
        StringBuilder ans = new StringBuilder();
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty())
        {
            TreeNode pollNode = que.poll();
            if (pollNode != null)
                ans.append(pollNode.val + "!");
            else
                ans.append("#!");
            if (pollNode != null)
            {
                que.add(pollNode.left);
                que.add(pollNode.right);
            }
        }
        return ans.toString();
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N, root;
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges = new int[N][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                edges[i][j] = in.nextInt();
        TreeNode rootNode = TreeNode.createTree(edges, root);
        // 同时这么搞, 会超时
        out.println(solutionEncodePre(solutionDecodePre(solutionEncodePre(rootNode))));
        out.println(solutionEncodeLevel(solutionDecodeLevel(solutionEncodeLevel(rootNode))));
        out.flush();
    }
}

CD164 遍历二叉树的神级方法❗

/* ❗morris❗ */
public class CD164_1
{
    public static class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int num)
        {
            this.val = num;
        }

        public static TreeNode createTree(int[][] edges, int root)
        {
            TreeNode[] treeNodes = new TreeNode[edges.length + 1];
            Arrays.setAll(treeNodes, TreeNode::new);
            for (int i = 0; i < edges.length; i++)
            {
                if (edges[i][1] != 0)
                    treeNodes[edges[i][0]].left = treeNodes[edges[i][1]];
                if (edges[i][2] != 0)
                    treeNodes[edges[i][0]].right = treeNodes[edges[i][2]];
            }
            return treeNodes[root];
        }
    }

    public static void solutionPre(TreeNode root)
    {
        if (root == null) return;
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur != null)
        {
            mostRight = cur.left;
            if (mostRight != null)
            {
                while (mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if (mostRight.right == null)
                {
                    mostRight.right = cur;
                    System.out.print(cur.val + " ");
                    cur = cur.left;
                    continue;
                }
                else
                    mostRight.right = null;
            }
            else
                System.out.print(cur.val + " ");
            cur = cur.right;
        }
        System.out.println();
    }

    public static void solutionIn(TreeNode root)
    {
        if (root == null) return;
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur != null)
        {
            mostRight = cur.left;
            if (mostRight != null)
            {
                while (mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if (mostRight.right == null)
                {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }
                else
                    mostRight.right = null;
            }
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
        System.out.println();
    }

    public static void solutionPos(TreeNode root)
    {
        if (root == null) return;
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur != null)
        {
            mostRight = cur.left;
            if (mostRight != null)
            {
                while (mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if (mostRight.right == null)
                {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }
                else
                {
                    mostRight.right = null;
                    printEdge(cur.left);
                }
            }
            cur = cur.right;
        }
        printEdge(root);
        System.out.println();
    }

    public static void printEdge(TreeNode root)
    {
        TreeNode tail = reverseEdge(root);
        TreeNode cur = tail;
        while (cur != null)
        {
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
        reverseEdge(tail);
    }

    public static TreeNode reverseEdge(TreeNode from)
    {
        TreeNode pre = null;
        TreeNode next = null;
        while (from != null)
        {
            next = from.right;
            from.right = pre;
            pre = from;
            from = next;
        }
        return pre;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, root;
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges = new int[N][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                edges[i][j] = in.nextInt();
        TreeNode rootNode = TreeNode.createTree(edges, root);
        solutionPre(rootNode);
        solutionIn(rootNode);
        solutionPos(rootNode);
    }
}

CD165 在二叉树中找到累加和为指定值的最长路径长度

/* (x->y) = (root->y) - (root->x) */
public class CD165_1
{
    public static class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int num)
        {
            this.val = num;
        }

        public static TreeNode createTree(int[][] edges, int root)
        {
            TreeNode[] treeNodes = new TreeNode[edges.length + 1];
            Arrays.setAll(treeNodes, TreeNode::new);
            for (int i = 0; i < edges.length; i++)
            {
                treeNodes[edges[i][0]].val = edges[i][3];
                if (edges[i][1] != 0)
                    treeNodes[edges[i][0]].left = treeNodes[edges[i][1]];
                if (edges[i][2] != 0)
                    treeNodes[edges[i][0]].right = treeNodes[edges[i][2]];
            }
            return treeNodes[root];
        }
    }

    public static int solution(TreeNode root, int SUM)
    {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] ans = new int[1];
        map.put(0, 0);
        inOrder(root, 0, 1, SUM, ans, map);
        return ans[0];
    }

    public static void inOrder(TreeNode root, int curSum, int depth, int SUM, int[] ans, HashMap<Integer, Integer> map)
    {
        if (root == null) return;
        curSum += root.val;
        if (!map.containsKey(curSum))
            map.put(curSum, depth);
        if (map.containsKey(curSum - SUM))
            ans[0] = Math.max(ans[0], depth - map.get(curSum - SUM));
        inOrder(root.left, curSum, depth + 1, SUM, ans, map);
        inOrder(root.right, curSum, depth + 1, SUM, ans, map);
        if (depth == map.get(curSum))
            map.remove(curSum);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, root, SUM;
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges = new int[N][4];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 4; j++)
                edges[i][j] = in.nextInt();
        SUM = in.nextInt();
        TreeNode rootNode = TreeNode.createTree(edges, root);
        System.out.println(solution(rootNode, SUM));
    }
}

CD166 找到二叉树中的最大搜索二叉子树⭐

/* ⭐树形DP⭐ */
public class CD166_1
{
    public static class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int num)
        {
            this.val = num;
        }

        public static TreeNode createTree(int[][] edges, int root)
        {
            TreeNode[] treeNodes = new TreeNode[edges.length + 1];
            Arrays.setAll(treeNodes, TreeNode::new);
            for (int i = 0; i < edges.length; i++)
            {
                if (edges[i][1] != 0)
                    treeNodes[edges[i][0]].left = treeNodes[edges[i][1]];
                if (edges[i][2] != 0)
                    treeNodes[edges[i][0]].right = treeNodes[edges[i][2]];
            }
            return treeNodes[root];
        }
    }

    public static int solution(TreeNode root)
    {
        //int[]{treeNode.val, treeSize, val.max, val.min}
        return posOrder(root)[1];
    }

    public static int[] posOrder(TreeNode root)
    {
        if (root == null) return null;
        int[] leftRes = posOrder(root.left);
        int[] rightRes = posOrder(root.right);
        if (root.left == null && root.right == null)
            return new int[]{root.val, 1, root.val, root.val};
        else if (root.left == null)
        {
            if (root.right.val == rightRes[0] && root.val < rightRes[3])
                return new int[]{root.val, 1 + rightRes[1], rightRes[2], root.val};
            else
                return new int[]{rightRes[0], rightRes[1], Integer.MAX_VALUE, Integer.MIN_VALUE};
        }
        else if (root.right == null)
        {
            if (root.left.val == leftRes[0] && root.val > leftRes[2])
                return new int[]{root.val, 1 + leftRes[1], root.val, leftRes[3]};
            else
                return new int[]{leftRes[0], leftRes[1], Integer.MAX_VALUE, Integer.MIN_VALUE};
        }
        else
        {
            if (root.left.val == leftRes[0] && root.right.val == rightRes[0] && root.val > leftRes[2] && root.val < rightRes[3])
                return new int[]{root.val, 1 + leftRes[1] + rightRes[1], rightRes[2], leftRes[3]};
            else
                return new int[]{leftRes[1] > rightRes[1] ? leftRes[0] : rightRes[0], Math.max(leftRes[1], rightRes[1]), Integer.MAX_VALUE, Integer.MIN_VALUE};
        }
    }


    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, root;
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges = new int[N][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                edges[i][j] = in.nextInt();
        TreeNode rootNode = TreeNode.createTree(edges, root);
        System.out.println(solution(rootNode));
    }
}

CD167 找到二叉树中符合搜索二叉树条件的最大拓扑结构❗

/* ❗(递归) 枚举每个节点, 统计个数❗ */
public class CD167_1
{
    public static class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int num)
        {
            this.val = num;
        }

        public static TreeNode createTree(int[][] edges, int root)
        {
            TreeNode[] treeNodes = new TreeNode[edges.length + 1];
            Arrays.setAll(treeNodes, TreeNode::new);
            for (int i = 0; i < edges.length; i++)
            {
                if (edges[i][1] != 0)
                    treeNodes[edges[i][0]].left = treeNodes[edges[i][1]];
                if (edges[i][2] != 0)
                    treeNodes[edges[i][0]].right = treeNodes[edges[i][2]];
            }
            return treeNodes[root];
        }
    }

    public static int solution(TreeNode root)
    {
        if (root == null) return 0;
        int ans = cal(root, root);
        ans = Math.max(ans, solution(root.left));
        ans = Math.max(ans, solution(root.right));
        return ans;
    }

    public static int cal(TreeNode root, TreeNode node)
    {
        if (node == null) return 0;
        if (judgeBinSearch(root, node))
            return 1 + cal(root, node.left) + cal(root, node.right);
        return 0;
    }

    public static boolean judgeBinSearch(TreeNode root, TreeNode node)
    {
        if (root == null) return false;
        if (root == node) return true;
        return judgeBinSearch(root.val > node.val ? root.left : root.right, node);
    }


    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, root;
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges = new int[N][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                edges[i][j] = in.nextInt();
        TreeNode rootNode = TreeNode.createTree(edges, root);
        System.out.println(solution(rootNode));
    }
}

/* ❗拓扑贡献记录❗ */
public class CD167_2
{
    public static class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int num)
        {
            this.val = num;
        }

        public static TreeNode createTree(int[][] edges, int root)
        {
            TreeNode[] treeNodes = new TreeNode[edges.length + 1];
            Arrays.setAll(treeNodes, TreeNode::new);
            for (int i = 0; i < edges.length; i++)
            {
                if (edges[i][1] != 0)
                    treeNodes[edges[i][0]].left = treeNodes[edges[i][1]];
                if (edges[i][2] != 0)
                    treeNodes[edges[i][0]].right = treeNodes[edges[i][2]];
            }
            return treeNodes[root];
        }
    }

    public static int solution(TreeNode root)
    {
        HashMap<TreeNode, int[]> map = new HashMap<>();
        return posOrder(root, map);
    }

    public static int posOrder(TreeNode root, HashMap<TreeNode, int[]> map)
    {
        if (root == null) return 0;
        int lRes = posOrder(root.left, map);
        int rRes = posOrder(root.right, map);
        modifyMap(root.left, root.val, map, true);
        modifyMap(root.right, root.val, map, false);
        int[] lArr = map.get(root.left);
        int[] rArr = map.get(root.right);
        int l = (lArr == null ? 0 : lArr[0] + lArr[1] + 1);
        int r = (rArr == null ? 0 : rArr[0] + rArr[1] + 1);
        map.put(root, new int[]{l, r});
        return Math.max(l + r + 1, Math.max(lRes, rRes));
    }

    public static void modifyMap(TreeNode root, int val, HashMap<TreeNode, int[]> map, boolean isLeft)
    {
        TreeNode temp = root;
        if (temp == null || !map.containsKey(temp)) return;
        while (temp != null && (!isLeft || temp.val < val) && (isLeft || temp.val > val))
        {
            if (!map.containsKey(temp)) return;
            if (isLeft) temp = temp.right;
            else temp = temp.left;
        }
        if (temp == null) return;
        int tl = map.get(temp)[0];
        int tr = map.get(temp)[1];
        map.remove(temp);
        while (root != temp)
        {
            int l = map.get(root)[0];
            int r = map.get(root)[1];
            if (isLeft)
            {
                map.put(root, new int[]{l, r - tl - tr - 1});
                root = root.right;
            }
            else
            {
                map.put(root, new int[]{l - tl - tr - 1, r});
                root = root.left;
            }
        }
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, root;
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges = new int[N][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                edges[i][j] = in.nextInt();
        TreeNode rootNode = TreeNode.createTree(edges, root);
        System.out.println(solution(rootNode));
    }
}

CD168 二叉树的按层打印与 ZigZag 打印

/* 模拟(左神用的双端队列) */
public class CD168_1
{
    public static class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int num)
        {
            this.val = num;
        }

        public static TreeNode createTree(int[][] edges, int root)
        {
            TreeNode[] treeNodes = new TreeNode[edges.length + 1];
            Arrays.setAll(treeNodes, TreeNode::new);
            for (int i = 0; i < edges.length; i++)
            {
                if (edges[i][1] != 0)
                    treeNodes[edges[i][0]].left = treeNodes[edges[i][1]];
                if (edges[i][2] != 0)
                    treeNodes[edges[i][0]].right = treeNodes[edges[i][2]];
            }
            return treeNodes[root];
        }
    }

    public static void solution(TreeNode root)
    {
        levelPrint(root);
        ziaPrint(root);
    }

    public static void levelPrint(TreeNode root)
    {
        if (root == null) return;
        int level = 1;
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty())
        {
            int size = que.size();
            System.out.print("Level " + level + " :");
            while (size-- > 0)
            {
                TreeNode pollNode = que.poll();
                System.out.print(" " + pollNode.val);
                if (pollNode.left != null) que.add(pollNode.left);
                if (pollNode.right != null) que.add(pollNode.right);
            }
            System.out.println();
            level++;
        }
    }

    public static void ziaPrint(TreeNode root)
    {
        if (root == null) return;
        int level = 1;
        Queue<TreeNode> que = new LinkedList<>();
        ArrayList<TreeNode> temp = new ArrayList<>();
        que.add(root);
        while (!que.isEmpty())
        {
            temp.clear();
            int size = que.size();
            while (size-- > 0)
            {
                TreeNode pollNode = que.poll();
                temp.add(pollNode);
                if (pollNode.left != null) que.add(pollNode.left);
                if (pollNode.right != null) que.add(pollNode.right);
            }
            if (level % 2 != 0)
            {
                System.out.print("Level " + level + " from left to right:");
                for (int i = 0; i < temp.size(); i++)
                    System.out.print(" " + temp.get(i).val);
            }
            else
            {
                System.out.print("Level " + level + " from right to left:");
                for (int i = temp.size() - 1; i >= 0; i--)
                    System.out.print(" " + temp.get(i).val);
            }
            System.out.println();
            level++;
        }
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, root;
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges = new int[N][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                edges[i][j] = in.nextInt();
        TreeNode rootNode = TreeNode.createTree(edges, root);
        solution(rootNode);
    }
}

CD169 调整搜索二叉树中两个错误的节点

/*
 * 模拟(中序排列中找降序)
 * 若在结构上交换这两个错误节点, 会有14种情况
 */
public class CD169_1
{
    public static class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int num)
        {
            this.val = num;
        }

        public static TreeNode createTree(int[][] edges, int root)
        {
            TreeNode[] treeNodes = new TreeNode[edges.length + 1];
            Arrays.setAll(treeNodes, TreeNode::new);
            for (int i = 0; i < edges.length; i++)
            {
                if (edges[i][1] != 0)
                    treeNodes[edges[i][0]].left = treeNodes[edges[i][1]];
                if (edges[i][2] != 0)
                    treeNodes[edges[i][0]].right = treeNodes[edges[i][2]];
            }
            return treeNodes[root];
        }
    }

    public static void solution(TreeNode root)
    {
        ArrayList<Integer> temp = new ArrayList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        inOrder(root, temp);
        for (int i = 0; i < temp.size() - 1; i++)
        {
            if (temp.get(i) > temp.get(i + 1))
            {
                ans.add(temp.get(i + 1));
                ans.add(temp.get(i));
            }
        }
        if (ans.size() == 2)
            System.out.println(ans.get(0) + " " + ans.get(1));
        else
        {
            int l = Math.max(ans.get(0), ans.get(1));
            int r = Math.min(ans.get(2), ans.get(3));
            System.out.println(Math.min(l, r) + " " + Math.max(l, r));
        }
    }

    public static void inOrder(TreeNode root, ArrayList<Integer> temp)
    {
        if (root == null) return;
        inOrder(root.left, temp);
        temp.add(root.val);
        inOrder(root.right, temp);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, root;
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges = new int[N][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                edges[i][j] = in.nextInt();
        TreeNode rootNode = TreeNode.createTree(edges, root);
        solution(rootNode);
    }
}

CD170 判断 t1 树是否包含 t2 树全部的拓扑结构

/* 枚举节点 */
public class CD170_1
{
    public static class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int num)
        {
            this.val = num;
        }

        public static TreeNode createTree(int[][] edges, int root)
        {
            TreeNode[] treeNodes = new TreeNode[500000 + 1];
            Arrays.setAll(treeNodes, TreeNode::new);
            for (int i = 0; i < edges.length; i++)
            {
                if (edges[i][1] != 0)
                    treeNodes[edges[i][0]].left = treeNodes[edges[i][1]];
                if (edges[i][2] != 0)
                    treeNodes[edges[i][0]].right = treeNodes[edges[i][2]];
            }
            return treeNodes[root];
        }
    }

    public static boolean solution(TreeNode root1, TreeNode root2)
    {
        if (root1 == null && root2 == null) return true;
        if (root1 == null) return false;
        return solution(root1.left, root2) || solution(root1.right, root2) || check(root1, root2);
    }

    public static boolean check(TreeNode root1, TreeNode root2)
    {
        if (root1 == null && root2 == null) return true;
        else if (root1 == null) return false;
        else if (root2 == null) return true;
        else
        {
            if (root1.val == root2.val)
                return check(root1.left, root2.left) && check(root1.right, root2.right);
            else return false;
        }
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, root;
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges1 = new int[N][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                edges1[i][j] = in.nextInt();
        TreeNode rootNode1 = TreeNode.createTree(edges1, root);
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges2 = new int[N][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                edges2[i][j] = in.nextInt();
        TreeNode rootNode2 = TreeNode.createTree(edges2, root);
        System.out.println(solution(rootNode1, rootNode2));
    }
}

CD171 判断 t1 树中是否有与 t2 树拓扑结构完全相同的子树

/* 枚举节点 */
public class CD171_1
{
    public static class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int num)
        {
            this.val = num;
        }

        public static TreeNode createTree(int[][] edges, int root)
        {
            TreeNode[] treeNodes = new TreeNode[500000 + 1];
            Arrays.setAll(treeNodes, TreeNode::new);
            for (int i = 0; i < edges.length; i++)
            {
                if (edges[i][1] != 0)
                    treeNodes[edges[i][0]].left = treeNodes[edges[i][1]];
                if (edges[i][2] != 0)
                    treeNodes[edges[i][0]].right = treeNodes[edges[i][2]];
            }
            return treeNodes[root];
        }
    }

    public static boolean solution(TreeNode root1, TreeNode root2)
    {
        if (root1 == null && root2 == null) return true;
        if (root1 == null) return false;
        return solution(root1.left, root2) || solution(root1.right, root2) || check(root1, root2);
    }

    public static boolean check(TreeNode root1, TreeNode root2)
    {
        if (root1 == null && root2 == null) return true;
        else if (root1 == null) return false;
        else if (root2 == null) return false;
        else
        {
            if (root1.val == root2.val)
                return check(root1.left, root2.left) && check(root1.right, root2.right);
            else return false;
        }
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, root;
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges1 = new int[N][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                edges1[i][j] = in.nextInt();
        TreeNode rootNode1 = TreeNode.createTree(edges1, root);
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges2 = new int[N][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                edges2[i][j] = in.nextInt();
        TreeNode rootNode2 = TreeNode.createTree(edges2, root);
        System.out.println(solution(rootNode1, rootNode2));
    }
}

/* 若t2树序列化是t1树序列化的字串, 则返回true */
public class CD171_2
{
    public static class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int num)
        {
            this.val = num;
        }

        public static TreeNode createTree(int[][] edges, int root)
        {
            TreeNode[] treeNodes = new TreeNode[500000 + 1];
            Arrays.setAll(treeNodes, TreeNode::new);
            for (int i = 0; i < edges.length; i++)
            {
                if (edges[i][1] != 0)
                    treeNodes[edges[i][0]].left = treeNodes[edges[i][1]];
                if (edges[i][2] != 0)
                    treeNodes[edges[i][0]].right = treeNodes[edges[i][2]];
            }
            return treeNodes[root];
        }
    }

    public static boolean solution(TreeNode root1, TreeNode root2)
    {
        return stringify(root1).contains(stringify(root2));
    }

    public static String stringify(TreeNode root)
    {
        if (root == null) return "#!";
        return root.val + "!" + stringify(root.left) + stringify(root.right);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N, root;
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges1 = new int[N][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                edges1[i][j] = in.nextInt();
        TreeNode rootNode1 = TreeNode.createTree(edges1, root);
        N = in.nextInt();
        root = in.nextInt();
        int[][] edges2 = new int[N][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                edges2[i][j] = in.nextInt();
        TreeNode rootNode2 = TreeNode.createTree(edges2, root);
        System.out.println(solution(rootNode1, rootNode2));
    }
}

标签：right,TreeNode,int,左神,面试,edges,二叉树,root,public
From： https://www.cnblogs.com/VividBinGo/p/17824951.html

相关文章

  • 秦疆的Java课程：24 基础 数据类型扩展及面试题讲解
    1、整数扩展进制二进制数：0b开头八进制数：0开头十六进制数：0x开头publicclassDEMO1{publicstaticvoidmain(String[]args){//整数扩展：进制intA=10;intB=0b10;//二进制intC=010;//八进制intD......
  • 面试必刷TOP101：24、二叉树的中序遍历
    题目题解深度优先搜索-递归publicclassSolution{/***代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可***@paramrootTreeNode类*@returnint整型一维数组*/publicint[]inorderTraversal(TreeNo......
  • Android并发编程高级面试题汇总（含详细解析 十二）
    Android并发编程高级面试题汇总最全最细面试题讲解持续更新中......
  • Android并发编程高级面试题汇总（含详细解析 十五）
    Android并发编程高级面试题汇总最全最细面试题讲解持续更新中......
  • 每天5道Java面试题(第7天)
    1. Files的常用方法都有哪些？Files.exists()：检测文件路径是否存在。Files.createFile()：创建文件。Files.createDirectory()：创建文件夹。Files.delete()：删除一个文件或目录。Files.copy()：复制文件。Files.move()：移动文件。Files.size()：查看文件个数。Files.read()：读取文件。......
  • 并发面试题
    并发面试题线程池线程池核心参数corePoolSize：核心线程池个数，通常情况下最多添加corePoolSize个Worker，当任务过多时（阻塞队列满了），会继续添加Worker直到Worker数达到maximumPoolSizeworkQueue：用于保存等待执行的任务的阻塞队列。比如基于数组的有界ArrayBlockQueue、基于链表的......
  • Android并发编程高级面试题汇总（含详细解析 十四）
    Android并发编程高级面试题汇总最全最细面试题讲解持续更新中......
  • 2023金九银十Android程序员面试题参考指南！
    前言还有不到一个礼拜就是金九银十招聘高峰期了，在这里分享一份《Android面试题汇总》这些面试题都是互联网大厂真实流出的面试内容，每个问题都附带完整详细的答案，不像网上的那些资料三教九流有的甚至还没答案，这些面试题都是我也是整理出来的精品资料。希望能给那些有需要朋友在求职......
  • Android并发编程高级面试题汇总（含详细解析 十一）
    Android并发编程高级面试题汇总最全最细面试题讲解持续更新中......
  • 02_二叉树的迭代遍历
    二叉树的迭代遍历//前序遍历顺序：中-左-右，入栈顺序：中-右-左classSolution{publicList<Integer>preorderTraversal(TreeNoderoot){List<Integer>result=newArrayList<>();if(root==null){returnresult;}St......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99