请问大家，刚才小红书笔试第二题二叉树的那道题怎么做？

感觉python写起来比较方便：https://www.cnblogs.com/ybf-yyj/p/9671437.html

import java.util.*; /**  * Created by jose on 2018/9/18.  */ public class Red2 {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         while (sc.hasNext()){             String line = sc.nextLine();             String[] levelarr = line.split(" ");             List<Integer> level = new ArrayList<>();             for (int i = 0; i <levelarr.length; i++) {                 level.add(Integer.valueOf(levelarr[i]));             }             line = sc.nextLine();             String[] midarr = line.split(" ");             int[] mid  = new int[midarr.length];             for (int i = 0; i < midarr.length; i++) {                 mid[i]= Integer.parseInt(midarr[i]);             }             boolean[] visited = new boolean[1024];             Node head = build(level,mid,visited,0,mid.length-1);             leaf(head);             System.out.println();             pre_visited(head);             System.out.println();             pos_visited(head);         }     }     static void leaf(Node node){         if(node==null) return;         if(node.left == null&&node.right==null) {             System.out.print(node.value+" ");         }         leaf(node.left);         leaf(node.right);     }     static void pre_visited(Node node){         if(node == null) return;         System.out.print(node.value+" ");         pre_visited(node.left);         pre_visited(node.right);     }     static void pos_visited(Node node){         if(node == null) return;         pos_visited(node.left);         pos_visited(node.right);         System.out.print(node.value+" ");     }     static class Node{         int value;         Node left;         Node right;     }     public static Node build(List<Integer> level,int[] mid,boolean[] visited,int left,int right){         if(level.size()==0) return null;         Node head = new Node();         head.value = level.get(0);         int pos=0;         for (int i = left; i <= right; i++) {             if (level.get(0) == mid[i]){                 pos=i;                 break;             }         }         int cleft = left;         int cright = pos-1;         for (int i = 0; i < 1024; i++) {             visited[i]=false;         }         for (int i = cleft; i <= cright; i++) {             visited[mid[i]] = true;         }         List<Integer> leftchild=new ArrayList<>();         List<Integer> rightchild=new ArrayList<>();         for (int i = 1; i < level.size(); i++) {             if(visited[level.get(i)]){                 leftchild.add(level.get(i));             }else {                 rightchild.add(level.get(i));             }         }         head.left=build(leftchild,mid,visited,left,cright);         head.right=build(rightchild,mid,visited,pos+1,right);         return head;     } }

我是根据层序和中序重建一棵树，然后遍历

class TreeNode(object):     def __init__(self,x):         self.val = x         self.left = None         self.right = None class Solution(object):     tree = None     pre = []     post = []     end = []     def preorder(self,root):         if not root:             return         self.pre.append(root.val)         self.preorder(root.left)         self.preorder(root.right)     def postorder(self,root):         if not root:             return         self.postorder(root.left)         self.postorder(root.right)         self.post.append(root.val)     def endnode(self,root):         if not root:             return []         queue1 = [root]         queue2 = []         while queue1:             cur = queue1.pop(0)             if not cur.left and not cur.right:                 self.end.append(cur.val)             if cur.left:                 queue2.append(cur.left)             if cur.right:                 queue2.append(cur.right)             if queue1 == []:                 queue1 = queue2                 queue2 = []     def build(self, sub_levelorder, sub_inorder):         if sub_inorder == []:             return None         root_value = sub_levelorder[0]         root = TreeNode(root_value)         index = sub_inorder.index(root_value)         left_sub_inorder = sub_inorder[:index]         right_sub_inorder = sub_inorder[index + 1:]         left_sub_levelorder,right_sub_levelorder = [],[]        # 按照层次遍历，第一个出现的就是根节点，然后找到中序中根节点的位置，分成左右两个子树的中序。再根据这个中序的序列，找到左右子树层次遍历的序列        # 考试的时候这一步没做好，一直做不出来，看了@ningshixian的做法。         for each in sub_levelorder[1:]:             if each in left_sub_inorder:                 left_sub_levelorder.append(each)             else:                 right_sub_levelorder.append(each)         root.left = self.build(left_sub_levelorder, left_sub_inorder)         root.right = self.build(right_sub_levelorder, right_sub_inorder)         return root     def buildTree(self, levelorder, inorder):         """         :type preorder: List[int]         :type inorder: List[int]         :rtype: TreeNode         """         if levelorder == [] or inorder == []:             return None         self.tree = self.build(levelorder, inorder)

Python解法 利用层序和中序递归创建二叉树，然后递归打印叶子节点，morris 前序后序遍历二叉树 # -*- coding=utf-8 -*- class TreeNode(): def __init__(self, val): self.val = val self.left = None self.right = None class Solution(): def recreate_tree(self, level, mid_order): if not level or not mid_order: return None root = TreeNode(level[0]) root_index = mid_order.index(level[0]) left_mid_order = mid_order[:root_index] right_mid_order = mid_order[root_index+1:] left_level = [item for item in level if item in left_mid_order] right_level = [item for item in level if item in right_mid_order] root.left = self.recreate_tree(left_level, left_mid_order) root.right = self.recreate_tree(right_level, right_mid_order) return root def morris_pre_traverse(self, root): if root is None: return None cur = root most_right = None while cur: most_right = cur.left if most_right: while most_right.right and most_right.right != cur: most_right = most_right.right if most_right.right is None: most_right.right = cur # 第一次到达即打印 print(cur.val, end=' ') cur = cur.left continue else: most_right.right = None else: # 没有左子树的只会到达一次 print(cur.val, end=' ') cur = cur.right print('') def print_leaf(self, root): if not root.left and not root.right: print(root.val, end=' ') return if root.left: self.print_leaf(root.left) if root.right: self.print_leaf(root.right) def morris_post_traverse(self, root): if root is None: return None cur = root most_right = None while cur: most_right = cur.left if most_right: while most_right.right and most_right.right != cur: most_right = most_right.right if most_right.right is None: most_right.right = cur cur = cur.left continue else: most_right.right = None # 在第二次到达时逆序打印cur节点的左子树的右边界 self.print_edge(cur.left) cur = cur.right # 逆序打印整个二叉树的右边界 self.print_edge(root) print('') def print_edge(self, node): tail = self.reverse_edge(node) temp = tail while temp: print(temp.val, end=' ') temp = temp.right self.reverse_edge(tail) def reverse_edge(self, node): pre = None while node: next_node = node.right node.right = pre pre = node node = next_node return pre if __name__ == "__main__": level = list(map(int, input().split())) mid_order = list(map(int, input().split())) ex = Solution() root = ex.recreate_tree(level, mid_order) ex.print_leaf(root) print('') ex.morris_pre_traverse(root) ex.morris_post_traverse(root)

利用层序和中序创建二叉树 然后遍历就行了。。

0.8和0.9感觉凉了

A了几道

+2

+1