给一个二叉查找树(Binary Search Tree)的前序遍历结果数组,打印出所有的叶子节点。
#include <vector> #include <string> #include <iostream> using namespace std; int findindex(int start, int end, vector<int>& a, int target) { int i; for (i = start; i <= end; ++i) { if (a[i] > target) return i; } return i; } void shit(int start, int end, vector<int>& a) { // cout << start << end << endl; if (start > end) return; else if (start == end) { cout << a[start] << " "; return; } else { int index = findindex(start+1, end, a, a[start]); if (index <= end) { shit(start+1, index-1, a); shit(index, end, a); } else { shit(start+1, index-1, a); } } } int main() { vector<int> gyh; char c; int t; do { scanf("%d", &t); gyh.push_back(t); scanf("%c", &c); } while (c == ' '); shit(0, gyh.size()-1, gyh); }
vector<int> findLeaves(vector<int>& arr) { unordered_set<int> non_leaves; stack<int> nodes; nodes.push(arr[0]); for (int i = 1; i < arr.size(); i++) { if (arr[i] < nodes.top()) { // arr[i]是 nodes.top()的左子节点 non_leaves.insert(nodes.top()); nodes.push(arr[i]); } else { int t; while (!nodes.empty() && arr[i] > nodes.top()) { t = nodes.top(); nodes.pop(); } nodes.push(arr[i]); non_leaves.insert(t); // arr[i]是最后一次出栈的元素的右子节点 } } vector<int> res; for (int i : arr) { if (!non_leaves.count(i)) res.push_back(i); } return res; }
#include <iostream> #include <vector> #include <sstream> #include <deque> using namespace std; class Solution{ public: vector<int> seachBinaryTreeLeave(vector<int>& nums){ if(nums.size()==1) return nums; vector<int> ans; int tmp=0; deque<int> board; for(int i=0;i<nums.size();i++){ if(!board.empty()&&nums[i]>board.back()&&board.back()<board.front()){ ans.push_back(board.back()); while(!board.empty()&&board.back()<nums[i]) board.pop_back(); } board.push_back(nums[i]); } if(!board.empty()) ans.push_back(board.back()); return ans; } }; int main(int argc,char* argv[]){ vector<int> nums; string str; getline(cin,str); stringstream s(str); int num; while(s>>num) nums.emplace_back(num); vector<int> ans=Solution().seachBinaryTreeLeave(nums); for(int i=0;i<ans.size();i++){ cout<<ans[i]; if(i!=ans.size()-1) cout<<" "; } cout<<endl; return 0; }
board.back()<board.front(),这句话为了判断是否转换到右子树了若满足叶子节点,则存储结果,然后再while循环,维持一个递减序列。最后还要判断deque中是否还有元素,因为最右端还有一个元素
class TreeNode(object): def __init__(self, val): self.val = val self.left = None self.right = None def reConstructBinaryTree(pre, tin): if len(pre) == 0: return elif len(pre) == 1: return TreeNode(pre[0]) else: tree = TreeNode(pre[0]) idx = tin.index(pre[0]) tree.left = reConstructBinaryTree(pre[1:idx + 1], tin[:idx]) tree.right = reConstructBinaryTree(pre[idx + 1:], tin[idx + 1:]) return tree def preorderTraversal(root): if not root: return stack = [root] while stack: node = stack.pop() if node.left is None and node.right is None: print(node.val, end=" ") if node.right: stack.append(node.right) if node.left: stack.append(node.left) if __name__ == "__main__": preorder = list(map(int, input().split())) inorder = sorted(preorder) tree = reConstructBinaryTree(preorder, inorder) preorderTraversal(tree)
Go 递归,思路:在前序遍历结果中,第一个大于根节点的即为右子树,在这之前的为左子树
package main import "fmt" import "io" func main() { var input int preOrder := []int{} for { _, err := fmt.Scan(&input) if err == io.EOF { break } preOrder = append(preOrder, input) } findLeafNode(preOrder, 0, len(preOrder) - 1) } func findLeafNode(arr []int, left, right int) { // 当在前序结果中范围缩小到一个值时,代表就是叶子节点 if left == right { fmt.Print(arr[left]) fmt.Print(" ") return } i := left + 1 // 开始遍历前序结果,寻找左右子树分界线(比根节点大的就是分界线) for ; i <= right; i++ { if arr[i] > arr[left] { // 如果第一个节点就比根节点大,说明全是右子树 if i == left { findLeafNode(arr, i + 1, right) } else { findLeafNode(arr, left + 1, i - 1) findLeafNode(arr, i, right) } break } // 没有比根节点大的,说明全是左子树 if i == right { findLeafNode(arr, left + 1, right) } } }
模拟前序遍历,找到左右子树的范围,若子树只有一个节点,加入到结果集。 import java.util.*; public class Main { private static List<Integer> res; public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); sc.close(); String[] ss = s.split(" "); int n = ss.length; int[] nums = new int[n]; res = new ArrayList<>(); for (int i = 0; i < n; i++) { nums[i] = Integer.parseInt(ss[i]); } dfs(nums, 0, n - 1); for (int r: res) { System.out.print(r + " "); } } private static void dfs(int[] nums, int left, int right) { if (left == right) { res.add(nums[left]); return; } else if (left > right) { return; } int root = nums[left]; //找到右子树的起点 int rightStart = left + 1; for (int i = left + 1; i <= right; i++) { if (nums[i] > root) { rightStart = i; break; } } if (nums[rightStart] > root) { dfs(nums, left + 1, rightStart - 1); dfs(nums, rightStart, right); } else { dfs(nums, left + 1, right); } } }
import java.io.*; import java.util.*; public class Main { static StringBuilder sb=new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.readLine(); String[] s=str.split(" "); int[] num=new int[s.length]; for(int i=0;i<s.length;i++){ num[i]=Integer.parseInt(s[i]); } helper(num,0,s.length-1); System.out.println(sb.toString()); } private static void helper(int[] num,int root,int right){ if(root==right){ sb.append(num[root]).append(' '); return; } boolean flag=true; int left=0; for(int i=root;i<=right;i++){ if(num[i]>num[root]&&flag){ left=i; flag=false; } } //只有一边子树 if(flag||left==root+1){ helper(num,root+1,right); } //有两边树 else { helper(num,root+1,left-1); helper(num,left,right); } } }
#include<iostream> #include<vector> #include<algorithm> #include<unordered_map> using namespace std; unordered_map<int, int> qtoz; void dfs(vector<int>& qf, vector<int>& zf, int l1, int r1, int l2, int r2, vector<int>& res) { if (l1 > r1 || l2 > r2) return; if (l1 == r1) { res.push_back(qf[l1]); return; } int root = qf[l1]; int k = qtoz[root], m = k - l2; dfs(qf, zf, l1 + 1, l1 + m, l2, k - 1, res); dfs(qf, zf, l1 + m + 1, r1, k + 1, r2, res); } int main() { vector<int> qf; int a = 0; while (cin >> a) { qf.push_back(a); while (getchar() != '\n') { cin >> a; qf.push_back(a); } vector<int> zf(qf.begin(), qf.end()); sort(zf.begin(), zf.end()); for (int i = 0; i < qf.size(); i++) { for (int j = 0; j < zf.size(); j++) { if (qf[i] == zf[j]) { qtoz[qf[i]] = j; break; } } } vector<int> res; dfs(qf, zf, 0, qf.size() - 1, 0, zf.size() - 1, res); for (int i = 0; i < res.size(); i++) cout << res[i] << ' '; cout << endl; qf.clear(); } return 0; }二叉查找树的中序遍历是递增数组,将输入的前序序列进行排序可得到中序遍历数组,根据前序和中序遍历序列可还原二叉树,则可找到所有的叶子节点。
#include <iostream> #include <vector> #include <queue> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int val_): val(val_), left(nullptr), right(nullptr) {} }; TreeNode* buildTree(vector<int>& nums, int start, int end, vector<int>& ans) { if (start >= end) return nullptr; TreeNode* node = new TreeNode(nums[start]); //cout << start << " " << node->val << endl; int lbegin = nums[start + 1] < nums[start] ? start + 1: start; int rbegin = end; for (int i = lbegin + 1; i < end; i++) { if (nums[i] > nums[start]) { rbegin = i; break; } } if (lbegin > start) node->left = buildTree(nums, lbegin, rbegin, ans); if (rbegin < end) node->right = buildTree(nums, rbegin, end, ans); if (node->left == nullptr && node->right == nullptr) ans.push_back(node->val); return node; }; int main() { vector<int> nums; int num; while (cin >> num) { nums.push_back(num); } int len = nums.size(); vector<int> ans; TreeNode* root = buildTree(nums, 0, len, ans); // bfs //queue<TreeNode*> q; //q.push(root); //vector<int> ans; //while (!q.empty()) //{ // int size_ = q.size(); // for (int i = 0; i < size_; i++) // { // TreeNode* tmp = q.front(); // q.pop(); // if (tmp->left == nullptr && tmp->right == nullptr) ans.push_back(tmp->val); // else{ // if (tmp->left) q.push(tmp->left); // if (tmp->right) q.push(tmp->right); // } // } //} for (auto i : ans) cout << i << " "; return 0; }
#include <iostream> #include <vector> #include <functional> using namespace std; int main() { int num; vector<int> nums; while (cin >> num) { nums.push_back(num); } vector<int> res; function<void(int,int)> findleaf = [&](int l, int r) { int cur = nums[l]; int left = -1, right = -1; for (int j = l+1; j < r; j++) { if (nums[j] < cur && left == -1) left = j; if (nums[j] > cur && right == -1) right = j; } if (left == -1 && right == -1) { res.push_back(cur); return; } if (left == -1) { findleaf(right, r); } else if (right == -1) { findleaf(left, r); } else { findleaf(left, right); findleaf(right, r); } }; findleaf(0, nums.size()); for (auto i : res) cout << i << " "; return 0; }找到左右子树的root,递归即可
import java.lang.*; import java.util.*; public class Main{ static class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int val){ this.val = val; } } public static void main(String[] args){ Scanner scanner = new Scanner(System.in); String[] strs = scanner.nextLine().split(" "); int[] ints = new int[strs.length]; for(int i = 0; i < strs.length; i++){ ints[i] = Integer.valueOf(strs[i]); } TreeNode root = new TreeNode(ints[0]); for(int i = 1; i < ints.length; i++){ insert(ints[i], root); } List<Integer> ret = new ArrayList<>(); back(root, ret); for(int i = 0; i < ret.size(); i++){ System.out.print(ret.get(i) + " "); } } public static void back(TreeNode root, List<Integer> ret){ if(root.left == null && root.right == null){ ret.add(root.val); } if(root.left != null){ back(root.left, ret); } if(root.right != null){ back(root.right, ret); } } public static void insert(int val, TreeNode root){ if(val < root.val){ if(root.left == null){ root.left = new TreeNode(val); }else{ insert(val, root.left); } }else{ if(root.right == null){ root.right = new TreeNode(val); }else{ insert(val, root.right); } } } }构造一下二叉树再查找
#include<bits/stdc++.h> using namespace std; int main(){ vector<int>array; int i,k=1; cin>>i; array.push_back(i); while(cin.get()!='\n'){ cin>>i; k++; array.push_back(i); } for(int j=1;j<=k;j++){ if(array[j]>array[j-1]){cout<<array[j-1]<<' ';} } cout<<array[k-1]; return 0; }秒杀!!!
tree=list(map(int,input().split())) #tree=[40, 31, 25, 20, 26, 33, 50, 42, 53] def findt(tree): if len(tree)<2: #return str(tree) return tree i=1 while (i<len(tree)) and tree[i]<=tree[0]: i+=1 if i==len(tree): return [tree[-1]] else: return findt(tree[1:i])+findt(tree[i:]) a=findt(tree) a=list(map(str,a)) #for i in a: # res+=' '+str(i) #print(res) print(' '.join(a))
import java.io.BufferedInputStream; import java.io.BufferedOutputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.Arrays; import java.util.Queue; import java.util.Scanner; /** * FindLeafNode class * * @author Soarkey * @date 2021/3/26 */ public class Main { private static Queue<Integer> queue; public static void main(String[] args) { Scanner in = new Scanner(new BufferedInputStream(System.in)); PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out)); while (in.hasNextInt()) { String s = in.nextLine(); findLeafNode(s); int n = queue.size(); for (int i = 0; i < n - 1; ++i) { out.print(queue.poll() + " "); } out.println(queue.poll()); } in.close(); out.close(); } public static void findLeafNode(String s) { String[] sp = s.split(" "); int n = sp.length; int[] preOrder = new int[n]; for (int i = 0; i < n; ++i) { preOrder[i] = Integer.parseInt(sp[i]); } int[] inOrder = new int[n]; System.arraycopy(preOrder, 0, inOrder, 0, n); Arrays.sort(inOrder); queue = new ArrayDeque<>(n - 1); buildBinarySearchTree(preOrder, 0, n - 1, inOrder, 0, n - 1); } public static void buildBinarySearchTree(int[] preOrder, int l1, int r1, int[] inOrder, int l2, int r2) { if (l1 > r1 || l2 > r2) { return; } int root = preOrder[l1]; int k = l2; for (int i = l2; i <= r2; ++i) { if (inOrder[i] == root) { k = i; break; } } boolean isLeafNode = true; if (k > l2) { // left child isLeafNode = false; buildBinarySearchTree(preOrder, l1 + 1, l1 + k - l2, inOrder, l2, k - 1); } if (k < r2) { // right child isLeafNode = false; buildBinarySearchTree(preOrder, l1 + k - l2 + 1, r1, inOrder, k + 1, r2); } if (isLeafNode) { queue.add(root); } } }
#include <bits/stdc++.h> using namespace std; vector<int> res; void getRes(vector<int>& left, vector<int>& right) { //int cnt = 0; int l = left.size(), r = right.size(); if (l == 1) { res.emplace_back(left[0]); } else if (l > 1) { vector<int> lleft, lright; int root = left[0]; for (int i = 1; i < l; ++i) { if (left[i] < root) { lleft.emplace_back(left[i]); } else { lright.emplace_back(left[i]); } } getRes(lleft, lright); } if (r == 1) { res.emplace_back(right[0]); } else if (r > 1){ vector<int> rleft, rright; int root = right[0]; for (int i = 1; i < r; ++i) { if (right[i] < root) { rleft.emplace_back(right[i]); } else { rright.emplace_back(right[i]); } } getRes(rleft, rright); } //return cnt; } int main() { vector<int> left, right; int root; scanf("%d", &root); int val; while (~scanf("%d", &val)) { if (val < root) { left.emplace_back(val); } else { right.emplace_back(val); } } if (left.size() == 0 && right.size() == 0) { cout << root; return 0; } getRes(left, right); for (int i = 0; i < res.size(); ++i) { cout << res[i] << ' '; } return 0; }
/排除法/
import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { ArrayList<Integer> arr=new ArrayList<>(); Scanner sr=new Scanner(System.in); String s=sr.nextLine(); StringBuilder sb=new StringBuilder(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i)!=' ') { sb.append(s.charAt(i)); }else { arr.add(Integer.parseInt(sb.toString() + "")); sb.setLength(0); } } arr.add(Integer.parseInt(sb.toString() + "")); solution(arr); } public static void solution(ArrayList<Integer> arr){ boolean[] brr=new boolean[arr.size()]; for (int i = 1; i < arr.size(); i++) { if (arr.get(i)<=arr.get(i-1))brr[i-1]=true; else { int tem=i-1; for (int j = i-1; j >=0 ; j--) { if (arr.get(j)>arr.get(tem)&&arr.get(j)<arr.get(i)){ tem=j; } } brr[tem]=true; } } for (int i = 0; i < arr.size(); i++) { if (!brr[i]) System.out.print(arr.get(i)+" "); } } }