class node { node *get_left(); node *get_right(); int get_data(); }找出值为val的最浅节点所在层数。
int find(node *root, int val).
/** * 找出值为val的最浅节点所在层数。 * * @param tree * @param val * @return */ public static int findVal(Tree tree, int val) { if (tree == null || tree.root == null) { return -1; } Queue<Node> que = new LinkedList<>(); que.add(tree.root); int levels = 0; while (!que.isEmpty()) { int length = que.size(); while (length > 0) { Node node = que.poll(); if (node.data == val) { return ++levels; } if (node.leftChild != null) que.add(node.leftChild); if (node.rightChild != null) que.add(node.rightChild); length--; } levels++; } return -1; }
//C#版 int find(node root,int val) { if(root == null) { return 0; } else{ if(root.get_data() == val) { return 1; } else { int left = find(root.get_left(),val); int right = find(root.get_right(),val); if(left == 0 && right == 0) { return 0; } else { return left+right+1; } } } }
//层序遍历
int find(TreeNode root, int val){ int deep = 0; if(root == null) return -1; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); boolean found = false; while(!queue.isEmpty()){ Queue<TreeNode> cur = new LinkedList<TreeNode>(); while(!queue.isEmpty()){ TreeNode temp = queue.poll(); if(temp.val == val){ found = true; break; } if(temp.left != null) cur.add(temp.left); if(temp.right != null) cur.add(temp.right); }//while deep++; while(!cur.isEmpty()){ queue.add(cur.poll()); }//while }//while if(!found) return -1; return deep; }
int find(node *root, int val) { if(NULL==root) return -1; std::queue<node*> Queue1,Queue2; std::queue<node*> *pLevel1 = &Queue1,*pLevel2 = &Queue2; int level = 1; Queue1.push(root); while((*pLevel1).size()!=0) { while(0!=pLevel1->size()) { if(val==pLevel1->front()->get_data()) { return level; } else { if(NULL!=pLevel1->front()->get_left()) pLevel2->push(pLevel1->front()->get_left()); if(NULL!=pLevel1->front()->get_right()) pLevel2->push(pLevel2->front()->get_right()); pLevel1->pop(); } } ++level; std::queue<node*> *temp = pLevel1; pLevel1 = pLevel2; pLevel2 = temp; } return -1; }
int find(node *root, int val) { if (root == NULL) { return -1; } if (root->get_data() == val) { return 1; } int left = find(root->get_left(), val); int right = find(root->get_right(), val); if (left != -1 && right != -1) return min(left, right); else if (left != -1) { return left; } else if (right != -1) { return right; } else { return -1; } }