题目:
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
解析:
比较两个二叉树是否相同采用将二叉树进行“先序遍历”,“中序遍历”和“后序遍历”,如果其中有两种遍历的结果相同,则这两个二叉树相等
代码:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { String ResultL1 = Front(p); String ResultL2 = Front(q); String ResultL3 = Middle(p); String ResultL4 = Middle(q); /* String ResultL5 = Last(p); String ResultL6 = Last(q); */ if(ResultL1.equals(ResultL2) && ResultL3.equals(ResultL4)){ return true; } else{ return false; } } public static String Front(TreeNode Tree){ if(Tree == null){ return "X"; } String strResult = ""; strResult += Tree.val; strResult += Front(Tree.left); strResult += Front(Tree.right); return strResult; } public static String Middle(TreeNode Tree){ if(Tree == null){ return "X"; } String strResult = ""; strResult += Middle(Tree.left); strResult += Tree.val; strResult += Middle(Tree.right); return strResult; } public static String Last(TreeNode Tree){ if(Tree == null){ return "X"; } String strResult = ""; strResult += Last(Tree.left); strResult += Last(Tree.right); strResult += Tree.val; return strResult; } }
网上高人的代码如下:添加了空树的判断
bool isSameTree(TreeNode *p, TreeNode *q) { // Start typing your C/C++ solution below // DO NOT write int main() function if (p == NULL && q == NULL) return true; else if (p == NULL || q == NULL) return false; return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right); }