//找出二叉树最大值的节点
class Solution {
public:
    /**
     * @param root the root of binary tree
     * @return the max node
     */
    TreeNode* maxNode(TreeNode* root) {
        if (root == NULL) return root;
        TreeNode* leftMax = root;
        TreeNode* rightMax = root;
        if (root->left != NULL) leftMax = maxNode(root->left);
        if (root->right != NULL) rightMax = maxNode(root->right);
        TreeNode* max = root;
        if (leftMax->val > max->val) max = leftMax;
        if (rightMax->val > max->val) max = rightMax;
        return max;
    }
};

//深度复制一个二叉树
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of binary tree
     * @return root of new tree
     */
    TreeNode* cloneTree(TreeNode *root) {
        if (root == NULL) return NULL;
        TreeNode* r = new TreeNode(root->val);
        if (root->left != NULL) r->left = cloneTree(root->left);
        if (root->right != NULL) r->right = cloneTree(root->right);
        return r;
    }
};

//找出二叉树的最大深度
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int maxDepth(TreeNode *root) {
        if (root == NULL) return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        if (left >= right) return left+1;
        else return right+1;
    }
};