二叉树

二叉树节点定义

struct BinTreeNode
{
	TreeNodeType val;
	BinTreeNode *left;
	BinTreeNode *right;
}

二叉树涉及算法思想

递归

递归要点：

1. 这个递归函数的功能是什么，怎样调用这个函数，即设计好递归函数的返回值和参数列表
2. 什么时候应该结束这个递归，它的边界条件（出口）是什么？
3. 在非边界情况时，怎样从第n层转变成第n+1层 (递推公式)
   注：
   递归思想最重要的一点就是：不要去关函数的内部细节【避免钻牛角尖，容易混】，只需要关注函数作用以及输入输出即可。

例：二叉树最大深度

给定一个二叉树，找出其最大深度。
实例：
3
/
9 20
/
15 7
最大深度 3

递归实现：：
1.函数功能->找出最大深度；返回值->最大深度（int型）；参数->节点指针
2.边界：当root为null时，返回高度为0；
3.获取最大高度->左子树与右子树中较大值+1

int maxDepth(TreeNode *root) {
        if(root == null) 
        	return 0;	//边界条件
        return (maxDepth(root->left)?maxDepth(root->right))maxDepth(root->left):maxDepth(root->right) + 1;	//获取最大值
    }
}

判断平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

解题思路：
边界条件：当成功递归到叶子结点后为真，
单层递归：左右子树的高度差是否大于1即小于2；
然后递归

bool isBalanced(struct TreeNode* root){
    if(root==NULL)
    return true;


    int left_h=maxDepth(root->left);
    int right_h=maxDepth(root->right);
    return abs(left_h-right_h)<2 &&isBalanced(root->left)&&isBalanced(root->right);
}

判断是否为子树

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:
给定的树 s:

   3
  / \

4 5
/
1 2
给定的树 t：

4
/
1 2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

解题思路：
边界条件：
【判断子树：即从某一节点开始，子树与该根节点对应的数相等
递归：根节点判断，然后从左右子树判断】
空树为任意树的子树，为真；
当递归到空节点是返回false;
相同树是特殊的子树

bool _isSametree(struct TreeNode*s,struct TreeNode*t)
{
    if(s==NULL&&t==NULL)
    return true;
    if(s==NULL||t==NULL)
    return false;

    return s->val==t->val&&_isSametree(s->left,t->left)&&_isSametree(s->right,t->right);
}

bool isSubtree(struct TreeNode* s, struct TreeNode* t){
    if(t==NULL)
        return true;
    if(s==NULL)
        return false;
    if(_isSametree(s,t))
    return true;

    return isSubtree(s->left,t)||isSubtree(s->right,t);
}