資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法律學用 C++ 找出二叉樹中第一個不匹配的葉節點
假設我們有兩棵二叉樹。我們需要找到兩個樹中第一個不匹配的葉子。如果沒有不匹配的葉子，那麼不顯示任何內容。
如果這是兩棵樹，那麼第一個不匹配的葉子是 11 和 15。
我們將會同時使用堆疊迭代訪問這兩棵樹的前序遍歷。我們將為不同的樹使用不同的堆疊。我們將會把節點推入堆疊，直到最上層的節點是葉子節點。比較兩個最上層的節點，如果相同，那麼進一步檢查，否則顯示這兩個堆疊的頂部元素。
示例
#include <iostream>
#include <stack>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node *getNode(int x) {
Node * newNode = new Node;
newNode->data = x;
newNode->left = newNode->right = NULL;
return newNode;
}
bool isLeaf(Node * t) {
return ((t->left == NULL) && (t->right == NULL));
}
void findUnmatchedNodes(Node *t1, Node *t2) {
if (t1 == NULL || t2 == NULL)
return;
stack<Node*> s1, s2;
s1.push(t1); s2.push(t2);
while (!s1.empty() || !s2.empty()) {
if (s1.empty() || s2.empty() )
return;
Node *top1 = s1.top();
s1.pop();
while (top1 && !isLeaf(top1)){
s1.push(top1->right);
s1.push(top1->left);
top1 = s1.top();
s1.pop();
}
Node * top2 = s2.top();
s2.pop();
while (top2 && !isLeaf(top2)){
s2.push(top2->right);
s2.push(top2->left);
top2 = s2.top();
s2.pop();
}
if (top1 != NULL && top2 != NULL ){
if (top1->data != top2->data ){
cout << "First non matching leaves are: "<< top1->data <<" "<< top2->data<< endl;
return;
}
}
}
}
int main() {
Node *t1 = getNode(5);
t1->left = getNode(2);
t1->right = getNode(7);
t1->left->left = getNode(10);
t1->left->right = getNode(11);
Node * t2 = getNode(6);
t2->left = getNode(10);
t2->right = getNode(15);
findUnmatchedNodes(t1,t2);
}輸出
First non matching leaves are: 11 15
更新於： 18-12-2019
92 次瀏覽
廣告