首页 > 代码库 > 三个二叉树的简单问题

三个二叉树的简单问题

本文给出三个二叉树的简单问题的答案,因其简单易懂,笔者就不多说了,直接上代码。

一.找出二叉树最大值的节点

//找出二叉树最大值的节点
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;
    }
};

 

三个二叉树的简单问题