有关二叉树中使用递归解决的问题:

有关二叉树中使用递归解决的问题:,第1张

有关二叉树找公共祖先的问题:

#找公共祖先:
#情况一:二叉树为二叉搜索树:(根据二叉搜索树的特性,使用一次遍历即可)

//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);

    }

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/759621.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-01
下一篇 2022-05-01

发表评论

登录后才能评论

评论列表(0条)

保存