欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树下

程序员文章站 2022-05-18 19:36:34
...
写在前面:上午看了星爷的新喜剧之王,由于之前感觉评分不高导致并没有上映就看的!看完觉得真的没有感到有多差,起码我是这样认为的!
  1. 输入一棵二叉树,判断该二叉树是否是平衡二叉树
package tree;

import java.util.HashMap;

/**
 * Create by IDEA
 * User: zhangqi
 * Date: 2019/3/28
 * Desc: 输入一棵二叉树,判断该二叉树是否是平衡二叉树
 */
public class BalanceTree {
    /**
     * 思路a:写一个方法递归遍历二叉树左右结点的深度,并判断深度差 如果大于1则不是平衡二叉树
     * @param root
     * @return
     */
    public boolean IsBalanced(TreeNode root) {
        HashMap<Integer, Boolean> map = new HashMap<>();
        map.put(1, true);
        depth(root, map);
        return map.get(1);
    }

    public int depth(TreeNode root, HashMap<Integer,Boolean> map){

        if (root == null) return 0;
        int left = depth(root.left,map);
        int right = depth(root.right,map);
        if(left-right>1 || right-left>1) map.put(1,false);
        return Math.max(left, right) + 1;
    }
}

  1. 输入一棵二叉树,求该树的深度
package tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Create by IDEA
 * User: zhangqi
 * Date: 2019/3/27
 * Desc: 输入一棵二叉树,求该树的深度
 */
public class TreeDepth {

    /**
     * 思路a:对二叉树进行层序遍历得出树的深度
     *
     * @param root
     * @return
     */
    public int treeDepth(TreeNode root) {
        HashMap<Integer, Boolean> map = new HashMap<>();
        map.put(1, true);
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        int deep = 0;
        int cur, width;
        queue.offer(root);
        while (!queue.isEmpty()) {
            width = queue.size();
            cur = 0;
            while (cur < width) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                cur++;
            }
            deep++;
        }
        return deep;
    }

    /**
     * 思路b:递归版本,不看答案很难想的出来
     * @param root
     * @return
     */
    public int treeDepth2(TreeNode root) {

        if (root == null) return 0;

        int left = treeDepth2(root.left);
        int right = treeDepth2(root.right);

        return Math.max(left, right) + 1;
    }


}

  1. 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向
package tree;

import java.util.Stack;

/**
 * Create by IDEA
 * User: zhangqi
 * Date: 2019/3/28
 * Desc: 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
 */
public class TreeToList {

    /**
     * 思路a:二叉搜索树也就是二叉查找树,左子树小于右子树,要求排序所以选择中序遍历
     *
     * @param root
     * @return
     */
    public TreeNode treeToList(TreeNode root) {

        if (root == null) return null;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        TreeNode pre = null; //保存上一结点
        boolean isFirst = true;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            if (isFirst) {
                root = p; //将起点赋予中序遍历的第一个
                pre = p;
                isFirst = false;
            } else {
                pre.right = p;
                p.left = pre;
                pre = p;
            }
            p = p.right;
        }
        return root;
    }


    /**
     * 递归功法果真天下无敌,现阶段我自认无法hold
     * <p>
     * 1.将左子树构造成双链表,并返回链表头节点;
     * 2.新增一个全局变量记录左子树的最后一个节点;
     * 3.如果左子树链表不为空的话,将当前root追加到左子树链表;
     * 4.将右子树构造成双链表,并返回链表头节点;
     * 5.如果右子树链表不为空的话,将该链表追加到root节点之后;
     * 6.根据左子树链表是否为空确定返回的节点。
     */
    // 记录子树链表的最后一个节点,终结点只可能为只含左子树的非叶节点与叶节点
    protected TreeNode leftLast = null;

    public TreeNode Convert(TreeNode root) {
        if (root == null)
            return null;
        if (root.left == null && root.right == null) {
            leftLast = root;// 最后的一个节点可能为最右侧的叶节点
            return root;
        }
        // 1.将左子树构造成双链表,并返回链表头节点
        TreeNode left = Convert(root.left);
        // 3.如果左子树链表不为空的话,将当前root追加到左子树链表
        if (left != null) {
            leftLast.right = root;
            root.left = leftLast;
        }
        leftLast = root;// 当根节点只含左子树时,则该根节点为最后一个节点
        // 4.将右子树构造成双链表,并返回链表头节点
        TreeNode right = Convert(root.right);
        // 5.如果右子树链表不为空的话,将该链表追加到root节点之后
        if (right != null) {
            right.left = root;
            root.right = right;
        }
        return left != null ? left : root;
    }

}

  1. 从上往下打印出二叉树的每个节点,同层节点从左至右打印
package tree;

import java.util.ArrayList;

/**
 * Create by IDEA
 * User: zhangqi
 * Date: 2019/3/31
 * Desc: 从上往下打印出二叉树的每个节点,同层节点从左至右打印
 */
public class LevelOrderTree {

    /**
     * 思路a:利用队列先进先出的特性
     * @param root
     * @return
     */
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {

        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<TreeNode> queue = new ArrayList<>();

        if (root == null) {
            return list;
        }
        queue.add(root);

        while (queue.size() != 0) {
            TreeNode tree = queue.remove(0);
            if (tree.left != null) {
                queue.add(tree.left);
            }
            if (tree.right != null) {
                queue.add(tree.right);
            }
            list.add(tree.val);
        }
        return list;
    }
}

  1. 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同
package tree;

/**
 * Create by IDEA
 * User: zhangqi
 * Date: 2019/3/31
 * Desc: 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同
 */
public class LastOrderTree {


    public class Solution {

        /**
         * 思路a:后序遍历左右根,递归比值大小
         * @param s
         * @return
         */
        public boolean VerifySquenceOfBST(int[] s) {

            if (s.length == 0) return false;
            if (s.length == 1) return true;

            return serch(s, 0, s.length - 1);
        }

        public boolean serch(int[] s, int start, int root) {
            if (start >= root) return true;
            int i = root;
            while (i > start && s[i - 1] > s[root]) i--;

            for (int j = start; j < i - 1; j++) {
                if (s[j] > s[root]) return false;
            }
            return serch(s, start, i - 1) && serch(s, i, root - 1);
        }
    }
}

  1. 请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的
package tree;

/**
 * Create by IDEA
 * User: zhangqi
 * Date: 2019/3/31
 * Desc: 请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的
 */
public class SymmetryTree {

    /**
     * 思路a:还是递归,只能多练习多思考了
     * @param root
     * @return
     */
    boolean isSymmetrical(TreeNode root) {
        if (root == null) return true;

        return s(root.left, root.right);
    }

    boolean s(TreeNode left, TreeNode right) {

        if (left == null) return right == null;

        if (right == null) return false;

        if (left.val != right.val) return false;

        return s(left.right, right.left) && s(left.left, right.right);
    }
}

相关标签: tree