从零开始算法之路 ----相同的树

曾经终败给现在 2022-01-11 04:19 250阅读 0赞

前言：小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）

题源：leetcode（[https://leetcode-cn.com/problems/same-tree/）][https_leetcode-cn.com_problems_same-tree]

题目描述：  
给定两个二叉树，编写一个函数来检验它们是否相同。  
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

**解决方案**：递归  
思路:  
1.找终止条件：当p和q相等或不相等时终止，因此return  
2.返回什么值：应该返回的自然是true或false  
3.每一步要做什么：判断p和q是否相等，有多种情况，具体看代码

核心代码：

bool isSameTree(TreeNode* p, TreeNode* q) { 
        bool record1,record2,record; 
    	//如果两棵树都为空则相同 
    	if(p == NULL && q == NULL) return true;
    	//如果两棵树都不为空但值不相等则不相同
    	else if(p != NULL && q != NULL && p->val != q->val) return false;
    	//如果两棵树一棵为空一棵不为空则不相同
    	else if( p != NULL && q == NULL || p == NULL && q != NULL) return false;
    		
    	//如果两棵树都不为空且值相等则继续向下判断 
    	if(p != NULL && q != NULL && p->val == q->val){ 
            //判断左子树 
     	    record1 = isSameTree(p->left, q->left);	    
     		record2 = isSameTree(p->right, q->right);
     		if(record1 ==true && record2 == true)
     		    record =true;
     		else
     		   record =false;
    	} 
    	return record; 
        }

完整代码：

#include<iostream>
    using namespace std;
    struct  TreeNode{ 
    	int val;
    	TreeNode *left;
    	TreeNode *right;
    	TreeNode(int x=0):val(x), left(NULL), right(NULL){  }
    };
    
    class Solution{ 
    	private:
    		TreeNode *root;
    	
    
    	public:
    	  Solution(int x = 0){  root = new TreeNode(x);}	
    	  //判断两棵树是否相等 
    	  bool isSameTree(TreeNode *p, TreeNode *q);
    	  //用前序遍历建立二叉树
    	  void createBinTree(TreeNode *&subTree); 
    	  //利用前序遍历以广义表形式输出二叉树
    	  void printBTree(TreeNode *BT); 
    	  //获得根节点
    	  TreeNode * getRoot(){ 
    	  	return root;
    	  } 
    	
    };
    
    //用前序遍历建立二叉树
    void Solution::createBinTree(TreeNode *&subTree){ 
    	//递归方式建立二叉树
    	int item;
    	if(1){ 
    		scanf("%d",&item);
    		if(item != 0) { 
    			subTree = new TreeNode(item);
    			if(subTree == NULL)
    			{ 
    				cerr<<"存储分配错误!";
    				exit(1);
    			}
    			//递归建立左子树
    			createBinTree(subTree->left);
    			//递归建立右子树
    			createBinTree(subTree->right); 	
    		}
    		else
    		//封闭指向空子树的指针 
    		    subTree = NULL;	
    	}
    }
    
    //利用前序遍历以广义表形式输出二叉树
    void Solution::printBTree(TreeNode *BT){ 
    	//树为空时，递归结束 
    	if(BT != NULL){ 
    		//输出根节点的值 
    		printf("%d",BT->val); 
    		if(BT->left != NULL || BT->right != NULL){ 
    			//输出左括号 
    			printf("(");
    			//输出左子树 
    			printBTree(BT->left); 
    			printf(",");
    			printBTree(BT->right);
    			printf(")"); 
    			
    		} 
    	} 
    	
    }
    
    //递归判断两棵树是否相同
    bool Solution::isSameTree(TreeNode *p, TreeNode *q){ 
    	bool record1,record2,record; 
    	//如果两棵树都为空则相同 
    	if(p == NULL && q == NULL) return true;
    	//如果两棵树都不为空但值不相等则不相同
    	else if(p != NULL && q != NULL && p->val != q->val) return false;
    	//如果两棵树一棵为空一棵不为空则不相同
    	else if( p != NULL && q == NULL || p == NULL && q != NULL) return false;
    		
    	//如果两棵树都不为空且值相等则继续向下判断 
    	if(p != NULL && q != NULL && p->val == q->val){ 
            //判断左子树 
     	    record1 = isSameTree(p->left, q->left);	    
     		record2 = isSameTree(p->right, q->right);
     		if(record1 ==true && record2 == true)
     		    record =true;
     		else
     		   record =false;
    	} 
    	return record; 				
    }
    
    int main(){ 
    	Solution s1;
    	TreeNode *root1,*root2;
    	s1.createBinTree(root1);
    	printf("root2\n");
    	s1.createBinTree(root2);
    	s1.printBTree(root1);
    	s1.printBTree(root2);
    	printf("\n"); 
    	printf("判断结果：%d",s1.isSameTree(root1,root2));	
    }

[https_leetcode-cn.com_problems_same-tree]: https://leetcode-cn.com/problems/same-tree/%EF%BC%89