#找公共祖先:
#情况一:二叉树为二叉搜索树:(根据二叉搜索树的特性,使用一次遍历即可)
//root为根结点,找结点p和q的公共祖先:
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode temp = root;
while (true) {
if (temp.val > p.val && temp.val > q.val) {
temp = temp.left;
} else if (temp.val < p.val && temp.val < q.val) {
temp = temp.right;
} else {
return temp;
}
}
}
#情况二:二叉树为普通二叉树:(这时就需要用到递归)
class Solution {
TreeNode ans;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root, p, q);
return ans;
}
public boolean dfs(TreeNode root, TreeNode p, TreeNode q){
if (root == null){
return false;
}
boolean lson = dfs(root.left, p, q);
boolean rson = dfs(root.right, p, q);
if ((lson&&rson)||((root.val == p.val||root.val == q.val)&&(lson||rson))){
ans = root;
}
return lson || rson || (root.val == p.val || root.val == q.val);
}
}
#判断是否为平衡二叉树:
public static boolean isBalanced(TreeNode root) {
return getHeight(root) != -1;
}
public static int getHeight(TreeNode root) {//返回当前根结点子树深度
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = getHeight(root.right);
if (rightHeight == -1) {
return -1;
}
int result;
if (Math.abs(leftHeight - rightHeight) > 1) {
result = -1;
} else {
result = Math.max(leftHeight, rightHeight) + 1;
}
return result;
}
#判断是否为二叉搜索后序遍历:
@Test//(剑指 Offer 33. 二叉搜索树的后序遍历序列)
//注意二叉搜索树的特征:
//使用递归:
public void test33() {
}
public static boolean verifyPostorder(int[] postorder) {
return recur(postorder, 0, postorder.length-1);
}
public static boolean recur(int[] postorder, int i, int j) {
if (i >= j) {
return true;
}
int p = i;
while (postorder[p] < postorder[j]) {
p++;
}
int m = p;
while (postorder[p] > postorder[j]) {
p++;
}
return p == j && recur(postorder, i, m - 1) && recur(postorder, m , j-1);
}
//找出二叉树中具体和为某值的具体路径:
@Test//(剑指 Offer 34. 二叉树中和为某一值的路径)
public void test34() {
}
//回溯法:
public static List<List<Integer>> pathSum(TreeNode root, int target) {
List<List<Integer>> list = new ArrayList<>();
List<Integer> tempList = new ArrayList<>();
backTracking(list, tempList, root, 0, target);
return list;
}
public static void backTracking(List<List<Integer>> list, List<Integer> tempList, TreeNode root, int sum, int target) {
if (root == null){
return;
}
tempList.add(root.val);
sum+=root.val;
if (root.left == null&&root.right == null&&sum == target){
list.add(new ArrayList<>(tempList));
}
backTracking(list, tempList, root.left, sum, target);//因为有两条
backTracking(list, tempList, root.right, sum, target);
sum-=root.val;
tempList.remove(tempList.size()-1);
}
//判断是否是对称二叉树:
@Test//(剑指 Offer 28. 对称的二叉树)
public void test28() {
}
public static boolean isSymmetric(TreeNode root) {
return check(root, root);
}
public static boolean check(TreeNode l, TreeNode r) {
if (l == null && r == null) {
return true;
}
if (l == null || r == null) {
return false;
}
return (l.val == r.val) && check(l.left, r.right) && check(l.right, r.left);
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)