LeetCode 题解（4）：二叉树-递归法

learn from cyc2018 and LeetCode

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

类似于链表，二叉树的很多问题也可以利用递归的方法简单地实现。

104. Maximum Depth of Binary Tree (easy)

问题描述

得到二叉树的深度。

题解

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        return 1 + max(maxDepth(root->left),maxDepth(root->right));
    }
private:
    int max(int a, int b){
        if(a > b)
            return a;
        return b;
    }
};

110. Balanced Binary Tree (easy)

问题描述

判断一个树是否是平衡的：

如果任意一个结点的两个子树高度差小于等于 1，那么该树是平衡的。

题解

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        int i = getDepth(root->left) - getDepth(root->right);
        if(isBalanced(root->left) && isBalanced(root->right) && i < 2 && i > -2)
            return true;
        return false;
        
    }
private:
    int getDepth(TreeNode* root){
        if(root == NULL) return 0;
        return 1 + max(getDepth(root->left), getDepth(root->right));
    }
    int max(int a, int b){
        if(a > b) return a;
        return b;
    }
};

543. Diameter of Binary Tree (easy)

问题描述

求二叉树的直径：即任意两个结点之间的最长距离。

题解

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        Depth(root);
        return result;
    }
private:
    int result = 0;
    int Depth(TreeNode* root){
        if(root == NULL) return 0;
        int left = Depth(root->left);
        int right = Depth(root->right);
        result = max(result, left+right);
        return max(left, right) + 1;
    }
    int max(int a, int b){
        if(a > b) return a;
        return b;
    }
};

问题描述

寻找二叉树的最长路径，其中该路径上所有的结点值相同。

题解

class Solution {
public:
    int longestUnivaluePath(TreeNode* root) {
        longestUnivaluePathStartWithRoot(root);
        return result;
    }
private:
    int result = 0;
    int longestUnivaluePathStartWithRoot(TreeNode* root){
        if(root == NULL) return 0;
        int left = longestUnivaluePathStartWithRoot(root->left);
        int right = longestUnivaluePathStartWithRoot(root->right);
        int leftpath = 0;
        int rightpath = 0;
        if(root->left != NULL && root->val == root->left->val)
            leftpath = 1 + left;
        if(root->right != NULL && root->val == root->right->val)
            rightpath = 1 + right;
        result = max(result, leftpath + rightpath);
        return max(leftpath, rightpath);
    }
    int max(int a, int b){
        if(a > b) return a;
        return b;
    }
};

226. Invert Binary Tree (easy)

问题描述

将所有的左右子树翻转。

题解

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL) return root;
        TreeNode* tmp = invertTree(root->left);
        root->left = invertTree(root->right);
        root->right = tmp;
        return root;
    }
};

617. Merge Two Binary Trees (easy)

问题描述

将两棵二叉树归并到一棵新的二叉树中。其中归并方法为：相同位置的结点值相加（如果其中一个结点为 null，则进行覆盖）。

题解

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1 == NULL) return t2;
        if(t2 == NULL) return t1;
        TreeNode* newTree = new TreeNode(t1->val + t2->val);
        newTree->left = mergeTrees(t1->left, t2->left);
        newTree->right = mergeTrees(t1->right, t2->right);
        return newTree;
    }
};

112. Path Sum (easy)

问题描述

给定一个值与一个二叉树，判断是否存在一个由根到叶子结点的路径，使得该路径所有结点之和等于给定值。

题解

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL) return false;
        if(root->left == NULL && root->right == NULL && sum == root->val)
            return true;
        else if(hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val))
            return true;
        return false;
    }
};

问题描述

寻找二叉树中满足如下条件的路径的个数：

该路径上所有值的和等于某特定值。

题解

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if (root == NULL) return 0;
        int ret = pathSumStartWithRoot(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
        return ret;
    }
private:
    // 必须将路径分为两类：由 root 开始的与两棵子树下包含的，否则会产生重复
    int pathSumStartWithRoot(TreeNode* root, int sum) {
        if (root == NULL) return 0;
        int ret = 0;
        if (root->val == sum) ret++;
        ret += pathSumStartWithRoot(root->left, sum - root->val) + pathSumStartWithRoot(root->right, sum - root->val);
        return ret;
    }
};

572. Subtree of Another Tree (easy)

问题描述

给定两棵非空二叉树 $s$ 和 $t$ 。判断 $t$ 是否与 $s$ 的某一子树完全相同（ $t$ 是否是 $s$ 的一棵子树）。

题解

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(s == NULL && t == NULL) return true;
        if(s == NULL) return false;
        if(t == NULL) return false;
        if(beSubtree(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t))
            return true;
        return false;
    }
private:
    bool beSubtree(TreeNode* s, TreeNode* t){
        if(s == NULL && t == NULL) return true;
        if(s == NULL || t == NULL) return false;
        if(s->val == t->val && beSubtree(s->left, t->left) && beSubtree(s->right, t->right))
            return true;
        return false;
    }
};

101. Symmetric Tree (easy)

问题描述

判断一棵二叉树是否是左右对称的。

题解

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        return symmetric(root->left, root->right);
        
    }
private:
    bool symmetric(TreeNode* t1, TreeNode* t2){
        if(t1 == NULL && t2 == NULL) return true;
        if(t1 == NULL || t2 == NULL) return false;
        if(t1->val == t2->val && symmetric(t1->left, t2->right) && symmetric(t1->right, t2->left))
            return true;
        return false;
    }
};

111. Minimum Depth of Binary Tree (easy)

问题描述

给定一个二叉树，寻找其最小深度（从根节点到所有叶子结点中的最短距离）。

题解

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == NULL) return 0;
        if(root->left == NULL)
            return 1 + minDepth(root->right);
        if(root->right == NULL)
            return 1 + minDepth(root->left);
        return 1 + min(minDepth(root->left), minDepth(root->right));
    }
private:
    int min(int a, int b){
        if(a < b) return a;
        return b;
    }
};

404. Sum of Left Leaves (easy)

问题描述

求二叉树所有左叶子结点值之和。

题解

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == NULL) return 0;
        if(isLeaf(root->left)) return root->left->val + sumOfLeftLeaves(root->right);
        return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
        
    }
private:
    bool isLeaf(TreeNode* root){
        if(root == NULL) return false;
        if(root->left == NULL && root->right == NULL)
            return true;
        return false;
    }
};

337. House Robber III (medium)

问题描述

一个小偷进入了一个新的区域来偷东西，这个区域由一个二叉树构成。小偷意识到，一天晚上不能同时偷两个直接相连的房间，如果二叉树的值表示小偷能在这个房间偷到的钱数，那么判断今晚小偷能在这片区域偷到的总金额。

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

题解

class Solution {
public:
    int rob(TreeNode* root) {
        if(root == NULL) return 0;
        int val1 = root->val;
        if(root->left != NULL)
            val1 += rob(root->left->left) + rob(root->left->right);
        if(root->right != NULL)
            val1 += rob(root->right->left) + rob(root->right->right);
        int val2 = rob(root->left) + rob(root->right);
        return max(val1, val2);
    }
private:
    int max(int a, int b){
        if(a > b) return a;
        return b;
    }
};

671. Second Minimum Node In a Binary Tree (easy)

问题描述

有一种特殊的二叉树，该树上所有的结点要么有 0 个孩子，要么有 2 个孩子，并且子结点的值一定大于等于父结点，那么求该二叉树上第二小的值为多少，如果不存在第二小的值，则返回 -1。

题解

class Solution {
public:
    int findSecondMinimumValue(TreeNode* root) {
        if(root == NULL || root->left == NULL) return -1;
        int l = root->left->val;
        int r = root->right->val;
        if(l == root->val)
            l = findSecondMinimumValue(root->left);
        if(r == root->val)
            r = findSecondMinimumValue(root->right);
        if(l == -1) return r;
        if(r == -1) return l;
        if(r > l) return l;
        return r;
    }
};

235. Lowest Common Ancestor of a Binary Search Tree (easy)

问题描述

给定一个二叉搜索树，寻找两个结点的最近共同祖先（LCA）。

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

题解

对于给定的两个子结点 $p$ 和 $q$, 它们有三种可能：

分别在根结点的左右子树中：那么显然 LCA 就是根节点。
均在左子树中：那么在左子树中递归。
均在右子树中：那么在右子树中递归。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL) return NULL;
        if(root == p) return p;
        if(root == q) return q;
        TreeNode* l = lowestCommonAncestor(root->left, p, q);
        TreeNode* r = lowestCommonAncestor(root->right, p, q);
        if(l != NULL && r != NULL)
            return root;
        if(l == NULL)
            return r;
        return l;
        
    }
};

LeetCode 题解（4）：二叉树-递归法

问题描述

题解

相关问题

问题描述

题解

相关问题

问题描述

题解

相关问题

问题描述

题解

相关问题

问题描述

题解

问题描述

题解

问题描述

题解

相关问题

问题描述

题解

相关问题

问题描述

题解

相关问题

问题描述

题解

问题描述

题解

相关问题

问题描述

题解

问题描述

题解

相关问题

问题描述

题解

相关问题

问题描述

题解

相关问题