二叉树入门题
1. 判断两颗树是否相同
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// 如何判断两颗树是否相同? 根相同 + 左右子树相同
// 如何判断根相同? 结构 + 值相同
if (p == null && q != null || p != null && q == null) {
return false;
}
if (p == null && q == null) {
return true;
}
if (p.val != q.val) {
return false;
}
// 走到这说明根相同 接下来判断左右子树是否相同
return isSameTree(p.left,q.left)
&& isSameTree(p.right,q.right);
}
}
时间复杂度分析:
假设,p树节点个数为N q树节点个数为M
时间复杂度为 O(min(N,M)), 因为最坏情况下遍历完节点少的树就停止了
2. 判断一颗树是否是另一颗树的子树
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// 如何判断两颗树是否相同? 根相同 + 左右子树相同
// 如何判断根相同? 结构 + 值相同
if (p == null && q != null || p != null && q == null) {
return false;
}
if (p == null && q == null) {
return true;
}
if (p.val != q.val) {
return false;
}
// 走到这说明根相同 接下来判断左右子树是否相同
return isSameTree(p.left,q.left)
&& isSameTree(p.right,q.right);
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) {
return false;
}
if(isSameTree(root,subRoot)) {
return true;
}
if(isSubtree(root.left,subRoot)) {
return true;
}
if(isSubtree(root.right,subRoot)) {
return true;
}
return false;
}
}
时间复杂度分析:
设树节点为M 子树节点为N
最坏情况下,树中每一个节点都判断一次(调用isSameTree) 时间复杂度为O(M*N)
3. 翻转一颗二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
if (root.left == null && root.right == null) {
return root;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
4. 判断一颗树是否是平衡二叉树
如何判断 平衡二叉树 ? 每颗树的左右高度差 <= 1
class Solution {
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int leftH = getHeight(root.left);
int rightH = getHeight(root.right);
if (Math.abs(leftH - rightH) <= 1
&& isBalanced(root.left) && isBalanced(root.right)) {
return true;
}
return false;
}
}
时间复杂度分析:
能否以O(N)时间复杂度 判断一颗树是否为平衡二叉树 ?
在计算高度的同时进行判断
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) >= 0;
}
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftH = getHeight(root.left);
int rightH = getHeight(root.right);
if (leftH >= 0 && rightH >= 0 && Math.abs(leftH - rightH) <= 1) {
return Math.max(leftH,rightH) + 1;
}else {
return -1;
}
}
}
5. 判断对称二叉树
class Solution {
public boolean isSymmetric(TreeNode root) {
return isSymmetricChild(root.left,root.right);
}
public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
// 判断根:
if (leftTree == null && rightTree != null
|| leftTree != null && rightTree == null) {
return false;
}
if (leftTree == null && rightTree == null) {
return true;
}
if (leftTree.val != rightTree.val) {
return false;
}
// 判断左右子树:
return isSymmetricChild(leftTree.left,rightTree.right)
&& isSymmetricChild(leftTree.right,rightTree.left);
}
}
标签:right,TreeNode,入门,二叉树,return,null,root,left From: https://www.cnblogs.com/xumu7/p/17972998