二叉树OJ题

带值的多层递归

对二叉树的递归性质做一个更好的补充。

提到二叉树的递归，我们首相想到的就是二叉树的深度优先遍历（根遍历）。对于求二叉树结点的个数，同样可以用递归来实现（带值的多层递归）。

1、二叉树的结点数

int TreeSize(BTNode* root)
{if (root == NULL)return 0;elsereturn 1 + TreeSize(root->_left) + TreeSize(root->_right);
}

同理可以补充：求叶子结点数、树的深度。

2、二叉树的叶子结点数

int TreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}else if(root->_left == NULL && root->_right == NULL){return 1;}else{return TreeLeafSize(root->_left) + TreeLeafSize(root->_right);}
}

3、二叉树深度

int TreeDepth(BTNode* root)
{if (root == NULL){return 0;}else{return 1 + (TreeDepth(root->_left) > TreeDepth(root->_left) ? TreeDepth(root->_left) : TreeDepth(root->_left));}
}

OJ题

对于OJ题的VS调试,我们通常造一颗伪树.
对于二叉树的OJ题解法又不懂的地方，可以通过代码一步步画递归图来理解，我在这里只画较为复杂的几个。

1、二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode），递归算法，迭代在C++中。

int TreeSize(struct TreeNode* root) {if (root == NULL)return 0;elsereturn 1 + TreeSize(root->left) + TreeSize(root->right);
}//求Tree的大小,用与内存开辟void _PreOrder(struct TreeNode* root, int* arr, int* pi) {if (root == NULL)return;/*假设树:A/ \ B   C*///第一次:arr[0]=根节点的值 i=i+1//第二次:arr[1]=左孩子的值 i++//第三次:左孩子的左孩子=NULL i不变//第四次:左孩子的右孩子=NULL i不变//第五次:arr[2]=右孩子的值 i++arr[*pi] = root->val;(*pi)++;//这两句相当于对结点的访问_PreOrder(root->left, arr, pi);_PreOrder(root->right, arr, pi);
}//递归的话不能直接用 preorderTraversal来递归，这样会开辟很多空间
int* preorderTraversal(struct TreeNode* root, int* returnSize) {int sz = TreeSize(root);int* retArr = (int*)malloc(sizeof(int) * sz);int i = 0;_PreOrder(root, retArr, &i);//i传地址才会改变否则返回时i的值不会改变*returnSize = sz;return retArr;
}

类似的：

2、二叉树的中序遍历

94. 二叉树的中序遍历 - 力扣（LeetCode）

3、二叉树的后序遍历

145. 二叉树的后序遍历 - 力扣（LeetCode）

4、单值二叉树

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

965. 单值二叉树 - 力扣（LeetCode）（把一颗二叉树看作 当前树、左子树、右子树）

bool isUnivalTree(struct TreeNode* root) {if (root == NULL)return true; //树空即单值if (root->left != NULL && root->val != root->left->val)return false;//当前树与左不等if (root->right != NULL && root->val != root->right->val)return false;//当前树与右不等return isUnivalTree(root->left) && isUnivalTree(root->right);//判断左子树和右子树
}

5、最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

相比于直接返回递归函数的计算，用两个变量存储，减少了重复的计算。

int maxDepth(struct TreeNode* root) {if(root==NULL)return 0;int leftDepth=maxDepth(root->left);int rightDepth=maxDepth(root->right);//return maxDepth(root->left)?maxDepth(root->right)...return leftDepth>rightDepth?leftDepth+1:rightDepth+1;
}

6、翻转二叉树

给定一棵二叉树的根节点 root，请左右翻转这棵二叉树，并返回其根节点

LCR 144. 翻转二叉树 - 力扣（LeetCode）（求二叉树的镜像）

//写法一：交换左右子树
struct TreeNode* flipTree(struct TreeNode* root) {if (root == NULL || (root->left == NULL && root->right == NULL))return root;struct TreeNode* tmp = root->left;root->left = root->right;root->right = tmp;flipTree(root->left);flipTree(root->right);return root;
}//解法二：利用返回值
struct TreeNode* flipTree(struct TreeNode* root) {if (root == NULL)return NULL;struct TreeNode* left = flipTree(root->left);struct TreeNode* right = flipTree(root->right);root->left = right;root->right = left;return root;
}

7、相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的

100. 相同的树 - 力扣（LeetCode）

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if (p == NULL && q == NULL)return true;if (p == NULL && q != NULL)return false;if (p != NULL && q == NULL)return false;if (p->val != q->val)return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

8、另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

572. 另一棵树的子树 - 力扣（LeetCode）

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {if (root == NULL)return false;if (isSameTree(root, subRoot))return true;return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

9、平衡二叉树

平衡二叉树：是指该树所有节点的左右子树的高度相差不超过 1。

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

110. 平衡二叉树 - 力扣（LeetCode）:

bool isBalanced(struct TreeNode* root) {if (root == NULL)return true;int lefth = maxDepth(root->left);int righth = maxDepth(root->right);int gap = abs(lefth - righth);if (gap <= 1) {return isBalanced(root->left) && isBalanced(root->right);} else {return false;}
}
//对于N个节点的二叉树：只要遍历所有的结点，时间复杂度就是O(N)
//这个算法
//最好的时间复杂度是：O(N)
//最坏的时间复杂度是：O(N^2)

可以把判断平衡二叉树的算法优化到O(N)吗？

1、时间复杂度大的原因：

用的是前序判断，每次调用都会重复计算高度。
存在大量的重复计算

2、优化

用后序判断。
在判断的同时计算数的高度。

（这里的优化是：后序求高度，减少了重复计算。较为复杂需要画图补充...）。

//后序判断优化
bool _isBalanced(struct TreeNode* root, int* pDepth) {if (root == NULL) {*pDepth = 0;return true;} else {int leftDepth = 0;if (_isBalanced(root->left, &leftDepth) == false)return false;int rightDepth = 0;if (_isBalanced(root->right, &rightDepth) == false)return false;if (abs(leftDepth - rightDepth) > 1)return false;*pDepth = leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;return true;}
}bool isBalanced(struct TreeNode* root) {int depth = 0;return _isBalanced(root, &depth);
}

10、构建二叉树

即：还原二叉树，给定一个先序遍历的字符串序列，要求还原二叉树，并中序遍历该二叉树。

这道题的重点在于还原二叉树（二叉树的构建是递归的）。

对于一个先序序列能否还原二叉树：(#代表空格)

完整的先序序列：abc##de#g##f###，可以还原整个二叉树。
不完整的先序序列：abcdegf，无法还原二叉树，需要和中序序列联合还原。

typedef struct TreeNode {char val;struct TreeNode* left;struct TreeNode* right;
} TreeNode;TreeNode* CreateTree(char* str, int* pi) {if (str[*pi] == '#') {(*pi)++;return NULL;} else {TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));if (root == NULL) {printf("%s\n", strerror(errno));exit(-1);}root->val = str[*pi];(*pi)++;root->left = CreateTree(str, pi);//左子树递归构建root->right = CreateTree(str, pi);//右子树递归构建return root;}
}
//中序遍历
void Inorder(TreeNode* root) {if (root == NULL)return;Inorder(root->left);printf("%c", root->val);Inorder(root->right);
}int main() {char str[100];scanf("%s", str);int i = 0;TreeNode* root = CreateTree(str, &i);Inorder(root);
}