Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Shortest path in binary tree
#include <iostream> #include <list> #include <vector> using namespace std; struct BinTree { int data; BinTree *left; BinTree *right; BinTree(int d, BinTree* l, BinTree* r): data(d), left(l), right(r) {} }; BinTree* LowestCommonAncestor(BinTree* root, int a, int b, list<BinTree*>& stackA, list<BinTree*>& stackB, bool& foundBoth) { if (!root) return NULL; if (a == root->data) { stackA.push_front(root); return root; } if (b == root->data) { stackB.push_front(root); return root; } BinTree* lhcLeft = LowestCommonAncestor(root->left, a, b, stackA, stackB, foundBoth); BinTree* lhcRight = LowestCommonAncestor(root->right, a, b, stackA, stackB, foundBoth); if (lhcLeft && lhcRight) { stackA.push_front(root); foundBoth = true; return root; } if (lhcLeft) { if (!foundBoth) if (lhcLeft->data == a) stackA.push_front(root); else stackB.push_front(root); return lhcLeft; } if (lhcRight) { if (!foundBoth) if (lhcRight->data == a) stackA.push_front(root); else stackB.push_front(root); return lhcRight; } return NULL; } void printStack(list<BinTree*>& l) { for (auto it = l.begin(); it != l.end(); ++it) cout << (*it)->data << " "; } // 4 // / \ // 2 8 // / \ / \ // 1 3 6 9 // / \ // 5 7 int main() { BinTree *h = new BinTree(7, NULL, NULL); BinTree *j = new BinTree(5, NULL, NULL); BinTree *g = new BinTree(9, NULL, NULL); BinTree *f = new BinTree(6, j, h); BinTree *e = new BinTree(3, NULL, NULL); BinTree *d = new BinTree(1, NULL, NULL); BinTree *c = new BinTree(8, f, g); BinTree *b = new BinTree(2, d, e); BinTree *a = new BinTree(4, b, c); list<BinTree*> sa,sb; bool foundBoth = false;; cout << LowestCommonAncestor(a, 1, 5, sa, sb, foundBoth)->data << endl; sa.reverse(); list<BinTree*> path; path.insert(path.end(), sa.begin(), sa.end()); path.insert(path.end(), sb.begin(), sb.end()); printStack(path); }
run
|
edit
|
history
|
help
0
Dar
Display all prime numbers upto N without sieve
single_digit
Meeting Time
Some-stuff
CPP - Ex 5
Subarray with 0 sum
OperatorOverload2
Test 7(2020)
Średnia bez zera