【100】Same Tree && 【104】Maximum Depth of Binary Tree

题目：

【100】Same Tree

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.

思路：

采用分治算法，若两个二叉树的根结点非空且相等，则分别判断其左右子树是否为Same Tree；若其中一个为空，则返回false；均为空则返回true；

代码实现：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if ( p == NULL || q == NULL ) return ( p == q ); return ( p->val == q->val ) && isSameTree( p->left , q->left ) && isSameTree( p->right , q->right ); } }; 【104】Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

思路：

同样可以使用分治算法。若根结点为NULL，则树高为0；否则树高则等于1+左右子树的最大高度。

代码实现：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { int depth; if (root == NULL) depth = 0 ; else depth = 1 + max( maxDepth(root->left) , maxDepth(root->right) ); return depth; } };