数据结构
网络
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 次浏览
广告