手机网站大全免费,济南商务网站建设,贸易公司网站源码,营销案例100例小故事及感悟1 问题
判断二叉树是不是对称#xff08;递归和非递归实现#xff09;
如下二叉树#xff0c;就是对称的二叉树 23 3 1 4 4 1
如下二叉树#xff0c;就是非对称的二叉树 23 3 1 4 4 2 2 代码实现
#include iostream
#in…1 问题
判断二叉树是不是对称递归和非递归实现
如下二叉树就是对称的二叉树 23 3 1 4 4 1
如下二叉树就是非对称的二叉树 23 3 1 4 4 2 2 代码实现
#include iostream
#include queueusing namespace std;#define true 1
#define false 0typedef struct Node
{int value;struct Node* left;struct Node* right;
} Node;int isSymmetricTree(Node *head);
int isSymmetric(Node *left, Node *right);
int isSymmetricTree1(Node *head);/**判断是否是对称二叉树递归实现*/
int isSymmetricTree(Node *head)
{if (head NULL){return true;} return isSymmetric(head, head);
}int isSymmetric(Node *left, Node *right)
{if (left NULL right NULL){return true;}if (left NULL || right NULL){return false;}if (left-value ! right-value){return false;}return isSymmetric(left-left, right-right) isSymmetric(left-right, right-left);
} /**判断是否是对称二叉树非递归实现*/
int isSymmetricTree1(Node *head)
{if (head NULL){return true;} std::queueNode * queue1;std::queueNode * queue2;queue1.push(head-left);queue2.push(head-right);while(!queue1.empty() || !queue2.empty()){Node *left queue1.front();Node *right queue2.front();if ((left ! NULL) (right NULL)){return false;}if ((left NULL) (right ! NULL)){return false;} //因为上面情况只包含left为NULL和right不为NULL以及left不为NULL和right为NULL//还包含2种情况left和right都为NULL,以及left和right都不为NULL,所以我们left-value和right-判断相等的时候//一定要记得对left和right都不是NULL的前提下才能调用-,下次切记看到指针-的时候需要判断指针是否为NULL//left和right都为NULL的时候我们直接对queue1和queue2进行pop()操作if (left right (left-value ! right-value)){return false;}queue1.pop();queue2.pop();if (left ! NULL){queue1.push(left-left);queue1.push(left-right);}if (right ! NULL){queue2.push(right-right);queue2.push(right-left);}}return true;
}int main()
{/* 2* 3 3 * 1 4 4 1 * */Node head1, node1, node2, node3, node4, node5, node6;Node head2, node7, node8;head1.value 2;node1.value 3;node2.value 3;node3.value 1;node4.value 4;node5.value 4;node6.value 1;head1.left node1;head1.right node2;node1.left node3;node1.right node4;node2.left node5;node2.right node6;node3.left NULL;node3.right NULL;node4.left NULL;node4.right NULL;node5.left NULL;node5.right NULL;node6.left NULL;node6.right NULL;if (isSymmetricTree(head1)){std::cout tree is symmertric std::endl;}else{std::cout tree is not symmertric std::endl;}if (isSymmetricTree1(head1)){std::cout tree is symmertric std::endl;}else{std::cout tree is not symmertric std::endl;}return 0;
} 3 运行结果
tree is symmertric
tree is symmertric
