在二叉树中使用递归解决问题

整理自leetcode

树结点定义如下：

Definition for a binary tree node.
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

代码:

int maxDepth(struct TreeNode *root) {
	
	int ld = 0;
	int rd = 0;
	if (NULL == root) return 0;
	if (root->left) ld = maxDepth(root->left);	// 左子树存在进行左递归
	if (root->right) rd = maxDepth(root->right);	// 右子树存在进行右递归
	return 1 + ((ld > rd) ? ld : rd);		// 本层递归结束比较左右子树的深度取大者相加
}

对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

代码:

bool recursion(struct TreeNode* left, struct TreeNode* right) {
	
	// 如果左子树和右子树均为空 返回真
	if (NULL == left && NULL == right) return true;
	else if (left == NULL || right == NULL) {
		// 其中一个不为空 返回假
		return false;
	}

	// 左结点的值是否等于右结点的值
	bool c1 = (left->val == right->val);
	// 左结点的左子树是否等于右结点的右子树
	bool c2 = recursion(left->left, right->right);
	// 左结点的右子树是否等于右结点的左子树
	bool c3 = recursion(left->right, right->left);
	// 如果同时成立
	if (c1&&c2&&c3) {
		return true;
	}
	else {
		return false;
	}
}

bool isSymmetric(struct TreeNode* root) {
	// 根 为空 返回正确
	if (root == NULL) {
		return true;
	}
	return recursion(root->left, root->right);
}

路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

代码:

bool hasPathSum(struct TreeNode* root, int sum) {

	if (NULL == root) return false;

	// 保证该结点为叶子结点的前提下 ，判断此时的sum是否和结点的值相等
	if (root->val == sum && NULL == root->left && NULL == root->right)
		return true;

	// 递归向下层遍历，出错直接执行 false
	if (hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val))
		return true;

	return false;

}