二叉树算法题
前言
单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回
true；否则返回false。
- 拿到根节点，和左右孩子比较
- 左孩子不为空就判断是否相等，右孩子同理
- 以相同方式递归左右子树
- 结束条件
- root为空，不影响，返回true
- 若不相等直接返回false
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isUnivalTree(struct TreeNode* root) { if (root == NULL) return true; if (root->left && root->val != root->left->val) return false; if (root->right && root->val != root->right->val) return false; return isUnivalTree(root->left) && isUnivalTree(root->right); }
相同的树
给你两棵二叉树的根节点
p和q，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
- 如果两个二叉树都为空，则两个二叉树相同。
- 如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
- 如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSameTree(struct TreeNode* p, struct TreeNode* q) { if (p == NULL && q == NULL) return true; 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); }
对称二叉树
给你一个二叉树的根节点
root， 检查它是否轴对称。（root不为空）
- 二叉树是否对称，即左右子树是否对称
- 把左右子树当做单独的两棵树来比较
- 在上面一道相同的树中，我们是通过同时递归两棵树的左子树判断是否相等，对右子树同理
- 而本题则是对称，即判断一棵树的左子树和右子树（以及右子树和左子树）是否相等
- 所以我们同时递归一棵树的左子树和另一棵树的右子树（以及前者的右子树和后者左子树）即可
- 将上面代码略微修改即可
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSameTree(struct TreeNode* p, struct TreeNode* q) { if (p == NULL && q == NULL) return true; if (p == NULL || q == NULL) return false; if (p->val != q->val) return false; return isSameTree(p->left, q->right) && isSameTree(p->right, q->left); } bool isSymmetric(struct TreeNode* root) { return isSameTree(root->left,root->right); }
另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树
- 思路很简单，依次递推，到每个结点时判断即可
- 在左子树或者右子树找到了直接返回就行，注意是
||不是&&
- 对于每个结点都当作根节点，来判断以这个结点为根节点的树和subRoot是否相等
- 判断相等还是使用上面的isSameTree方法
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSameTree(struct TreeNode* p, struct TreeNode* q) { if (p == NULL && q == NULL) return true; 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); } 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); }
二叉树的前序遍历
给你二叉树的根节点
root，返回它节点值的前序遍历。
- 本题的特殊之处在于它的返回值是一个数组，所以我们需要先为数组动态开辟一块空间
- 第一步：计算二叉树结点个数
- 第二步：前序遍历并依次插入
- 自己写一个前序遍历函数
- 在插入时，使用传址调用的方式。不能创建全局变量，否则只能调用一次这个函数
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ typedef struct TreeNode TreeNode; int TreeSize(TreeNode* root) { if(root==NULL) return 0; return 1+TreeSize(root->left)+TreeSize(root->right); } void Preorder(TreeNode* root,int* arr,int* pi) { if(root==NULL) return; arr[(*pi)++]=root->val; Preorder(root->left,arr,pi); Preorder(root->right,arr,pi); } int* preorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize=TreeSize(root); int* arr=(int*)malloc(sizeof(int)*(*returnSize)); int i=0; Preorder(root,arr,&i); return arr; }
本题如换做中序和后序遍历，直接调换插入数据顺序即可，其它思路都一样
