TreeAndGraph(树和图)

1.实现一个函数,检查二叉树是否平衡。在这个问题中,平衡树的定义如下:任意一个结点,其两棵子树的高度差不超过1。

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    public TreeNode(int value) {
        this.data = value;
        this.left = null;
        this.right = null;
    }
}
public class BalanceTree {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

    }
    
    public static int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }
    
    public static boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int heightDiff = getHeight(root.left) - getHeight(root.right);
        if (Math.abs(heightDiff) > 1) {
            return false;
        } else {
            return isBalanced(root.left) && isBalanced(root.right);
        }
    }

}
View Code

思路:上述代码直接递归访问整棵树,计算每个结点两棵子树的高度。虽然可行,但是效率不高,getHeight会被反复调用计算同一个结点的高度。这个算法的时间复杂度为o(NlogN)。

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    public TreeNode(int value) {
        this.data = value;
        this.left = null;
        this.right = null;
    }
}
public class BalanceTree {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

    }
    
    public static int checkHeight(TreeNode root) {
        if (root == null) {
            return 0;//高度为0
        }
        //检查左子树是否平衡
        int leftHeight = checkHeight(root.left);
        if (leftHeight == -1) {
            return -1;//不平衡
        }
        //检查右子树是否平衡
        int rightHeight = checkHeight(root.right);
        if (rightHeight == -1) {
            return -1;//不平衡
        }
        //检查当前结点是否平衡
        int heightDiff = leftHeight - rightHeight;
        if (Math.abs(heightDiff) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
    
    public static boolean isBalanced(TreeNode root) {
        if (checkHeight(root) == -1) {
            return false;
        } else {
            return true;
        }
    }

}
View Code

改进的算法会从根节点递归向下检查每棵子树的高度。通过checkHeight方法,以递归方式获取每个结点左右子树的高度。若子树是平衡的,则checkHeight返回该子树的实际高度。                  若子树不平衡,则checkHeight会立即中断执行,并返回-1。该算法的时间复杂度为o(N),空间复杂度为o(H),其中H为树的高度。

2.给定有向图,设计一个算法,找出两个结点之间是否存在一条路径。

思路:只需通过图的遍历,BFS或DFS就能解决问题。从两个结点的其中一个出发,在遍历过程中,检查是否找到另一个结点。

          访问过的结点都应标记为“已访问”,以免循环和重复访问结点。

    public enum State {
        Unvisited, Visited, Visiting;
    } 
    public static boolean search(Graph g,Node start,Node end) {  
        LinkedList<Node> q = new LinkedList<Node>();
        for (Node u : g.getNodes()) {
            u.state = State.Unvisited;
        }
        start.state = State.Visiting;
        q.add(start);
        Node u;
        while(!q.isEmpty()) {
            u = q.removeFirst();
            if (u != null) {
                for (Node v : u.getAdjacent()) {
                    if (v.state == State.Unvisited) {
                        if (v == end) {
                            return true;
                        } else {
                            v.state = State.Visiting;
                            q.add(v);
                        }
                    }
                }
                u.state = State.Visited;
            }
        }
        return false;
    }
View Code

3.给定一个有序整数数组,元素各不相同且按升序排列,编写一个算法,创建一棵高度最小的二叉查找树。

思路:要创建一棵高度最小的二叉树,必须让左右子树的结点数量越接近越好。即让数组的中间值成为根节点,数组左边一半成为左子树,右边一半成为右子树。然后以类似的方式构造整棵树。数组每一区段的中间元素成为子树的根节点,左半部分成为左子树,右半部分成为右子树。以递归方式调用createMinimalBST方法,该方法会传入数组的一个区段,并返回最小树的根节点。该算法简述如下:(1)将数组中间位置的元素插入树中。(2)将数组左半边元素插入左子树。(3)将数组右半边元素插入右子树。(4)递归处理。

public TreeNode createMinimalBST(int arr[], int start, int end){
        if (end < start) {
            return null;
        }
        int mid = (start + end) / 2;
        TreeNode n = new TreeNode(arr[mid]);
        n.left = createMinimalBST(arr, start, mid - 1);
        n.right = createMinimalBST(arr, mid + 1, end);
        return n;
    }
    
 public  TreeNode createMinimalBST(int array[]) {
        return createMinimalBST(array, 0, array.length - 1);
    }
View Code

4.给定一棵二叉树,设计一个算法,创建含有某一深度上所有结点的链表(比如,若一棵树的深度为D,则会创建出D个链表)。

思路:可以用任意方法遍历整棵树,只要记住结点位于哪一层即可。

解法一:将前序遍历算法(根->左->右)稍作修改,将level+1传入下一个递归调用。使用深度优先搜索实现。

    public static void createLevelLinkedList(TreeNode root, ArrayList<LinkedList<TreeNode>> lists, int level) {
        if (root == null) {
            return;//终止条件
        }
        LinkedList<TreeNode> list = null;
        //得到list
        if (lists.size() == level) {//该层不在链表中
            list = new LinkedList<TreeNode>();
            lists.add(list);//将该层添加到链表末端
        } else {
            list = lists.get(level);
        }
        list.add(root);
        createLevelLinkedList(root.left, lists, level + 1);
        createLevelLinkedList(root.right, lists, level + 1);
    }
    
    public static ArrayList<LinkedList<TreeNode>> createLevelLinkedList(TreeNode root) {
        ArrayList<LinkedList<TreeNode>> lists = new ArrayList<LinkedList<TreeNode>>();
        createLevelLinkedList(root, lists, 0);
        return lists;
    }
View Code

解法二:对广度优先搜索稍加修改,即从根节点开始迭代,然后第2层,第3层等等。处于第i层时,表明已访问过第i-1层的所有结点。也就是说,要得到i层的结点,只需直接查看i-1层结点的所有子结点即可。

    public static ArrayList<LinkedList<TreeNode>> createLevelLinkedList(TreeNode root) {
        ArrayList<LinkedList<TreeNode>> result = new ArrayList<LinkedList<TreeNode>>();
        LinkedList<TreeNode> current = new LinkedList<TreeNode>();
        if (root != null) {
            current.add(root);
        }
        while (current.size() > 0) {//当前层不为空
            result.add(current);//加入当前层
            LinkedList<TreeNode> parents = current;//转到下一层
            current = new LinkedList<TreeNode>();//清空,装下一层
            for (TreeNode parent : parents) {
                if (parent.left != null) {
                    current.add(parent.left);
                }
                if (parent.right != null) {
                    current.add(parent.right);
                }
            }
        }
        return result;
    }
View Code

两者的时间复杂度都是o(N)。在空间复杂度方面,两者都要返回o(N)数据,因此第一种解法递归实现所需的额外o(logN)空间,跟必须传回的o(N)数据相比,并不算多。从大O记法的角度看,两者效率是一样的。

5.实现一个函数,检查一棵二叉树是否为二叉查找树。

解法一:中序遍历(左->根->右),将所有元素复制到数组中,然后检查该数组是否有序。问题在于,无法正确处理树中的重复值。代码实现基于树中不包含重复值的假设。 

    public static int last_printed = Integer.MIN_VALUE;//记录与当前元素比较的最后元素
    public static boolean checkBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        //递归检查左子树
        if (!checkBST(root.left)) {
            return false;
        }
        //检查当前根结点
        if (root.data <= last_printed) {
            return false;
        }
        last_printed = root.data;
        //递归检查右子树
        if (!checkBST(root.right)) {
            return false;
        }
        return true;//全部检查完毕
    }
View Code

解法二:满足二叉查找树的条件:所有左边的结点必须小于或等于当前结点,而当前结点必须小于所有右边的结点。

利用这一点,可以通过自上而下传递最小和最大值来解决问题。在迭代遍历整个树的过程中,用逐渐变窄的范围来检查各个结点。首先,从(min=INT_MIN,max=INT_MAX)这个范围开始检查根结点,处理左子树时,更新max。处理右子树时,更新min。只要有任一结点不能通过检查,则停止并返回false。

时间复杂度为O(N),N为整棵树的结点数,已是最佳做法。对于平衡树,空间复杂度为O(logN)。

    public boolean checkBST(TreeNode root) {
        return checkBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    public boolean checkBST(TreeNode root, int min, int max) {
        if (root == null) {
            return true;
        }
        if (root.data < min || root.data >= max) {
            return false;
        }
        if (!checkBST(root.left, min, root.data) || !checkBST(root.right, root.data, max)) {
            return false;
        }
        return true;
        //return (min < root.data && root.data< max) && checkBST(root.left, min, root.data) && checkBST(root.right, root.data, max);
    }
View Code

记住,在递归算法中,一定要确定终止条件以及结点为空的情况得到妥善处理。

6.设计一个算法,找出二叉查找树中指定结点的“下一个”结点(也即中序后继)。可以假定每个结点都含有指向父节点的连接。

思路:假定我们有一个假想的结点,访问顺序是左子树、当前结点、右子树。显然,下一个结点应该位于右边。

          到底是右子树的哪个结点呢?如果中序遍历右子树,它就是接下来第一个被访问的结点,也就应该是右子树最左边的结点。

          但是若这个结点没有右子树呢?若结点n没有右子树,就表示已遍访n的子树。必须回到n的父节点,记作q。

          若n在q的左边,下一个我们应该访问的结点就是q(中序遍历(左->根->右))。若n在q的右边,则表示已遍访q的子树。需要从q往上访问,直至找到还未完全遍访过的结点x。

          怎么才能知道还未完全遍历结点x呢?左结点已完全遍历,但其父结点尚未完全遍历。

          如果一路往上遍访这棵树都没发现左结点呢?说明已位于树的最右边,不会再有中序后继,返回NULL。

    public static TreeNode inorderSucc(TreeNode node) {
        //处理结点为空的情况
        if (node == null) {
            return null;
        }
        
        if (node.right != null) {//node有右子树
            return leftMostChild(node.right);//返回右子树的最左边结点
        } else {
            TreeNode q = node;
            TreeNode x = q.parent;//node的父节点
            while (x != null && x.left != q) {//直至q是其父节点的左子树
                q = x;
                x = x.parent;
            }
            return x;//返回当前根结点x
        }
    }
    
    public static TreeNode leftMostChild(TreeNode node) {
        if (node == null) {
            return null;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
View Code

7.设计并实现一个算法,找出二叉树中某两个结点的第一个共同祖先。不得将额外的结点储存在另外的数据结构中。注意:这不一定是二叉查找树。

解法:《九章算法》chapter three LCA最近公共祖先I II III

8.你有两棵非常大的二叉树:T1,有几百万个结点;T2,有几百个结点。设计一个算法,判断T2是否为T1的子树。如果T1有这么一个结点n,其子树与T2一模一样,则T2为T1的子树。也就是说,从结点n处把树砍断,得到的树与T2完全相同。

思路:在规模较小且较简单的问题中,可以创建一个字符串,表示中序和前序遍历(中序+前序遍历确定一棵树)。若T2前序遍历是T1前序遍历的子串,并且T2中序遍历是T1中序遍历的子串,则T2为T1的子树,利用后缀树可以在线性时间内检查是否为子串。

解法:鉴于该问题指定的约束条件,方法是搜遍较大的那棵树T1。每当T1的某个结点与T2的根节点匹配时,就调用treeMatch。treeMatch方法会比较两棵子树,检查两者是否相同。

    boolean containsTree(TreeNode t1, TreeNode t2) {
        if (t2 == null) {//空树一定是子树
            return true;
        }
        return subTree(t1, t2);
    }
    boolean subTree(TreeNode r1, TreeNode r2) {
        if (r1 == null) {
            return false;//大的树已经空了,还未找到子树
        }
        if (r1.data == r2.data) {
            if (matchTree(r1, r2)) {
                return true;
            }
        }
        return (subTree(r1.left, r2) || subTree(r1.right, r2));
    }
    boolean matchTree(TreeNode r1, TreeNode r2) {
        if (r1 == null && r2 == null) {//若两者都为空
            return true;//子树中已无结点
        }
        if (r1 == null || r2 == null) {//若其中之一为空,但并不同时为空
            return false;
        }
        if (r1.data != r2.data) {//结点数据不匹配
            return false;
        }
        return (matchTree(r1.left, r2.left) && matchTree(r1.right, r2.right));
    }
View Code

运行时间粗略一看是O(NM),N为T1结点数,M为T2结点数。但实际上不必对T2的每个结点调用treeMatch,而是会调用k次,其中k为T2根节点在T1中出现的次数。因此,运行时间接近于O(n+km)。即使这样运行时间也有所夸大。即使根结点相同,一旦发现T1和T2有结点不同,就会退出treeMatch。因此每次调用treeMatch,也不见得都会查看m个结点。

9.给定一棵二叉树,其中每个结点都含有一个数值。设计一个算法,打印结点数值总和等于某个给定值的所有路径。注意,路径不一定非得从二叉树的根结点或叶结点开始或结束。

【可能有个隐含条件:必须是向下的路径,即结点的层级逐个递增。】

《九章算法》chapter three 二叉树的路径和II

思路:运用简化推广法来解题。

部分1:简化——假设路径必须从根节点开始,但可以在任意结点结束,怎么解决?

可以从根结点开始,向左向右访问子结点,计算每条路径上到当前结点为止的数值总和,若与给定值相同则打印当前路径。注意,就算找到总和,仍要继续访问这条路径。因为这条路径可能继续往下经过a+1结点和a-1结点(或其他数值总和为0的结点序列),完整路径的总和仍然等于sum。

部分2:推广——路径可从任意结点开始。在这种情况下,对于每个结点,我们都会向“上”检查是否得到相符的总和。也就是说不再要求“从这个结点开始是否会有总和为给定值的路径”,而是关注“这个结点是否为 总和为给定值的 某条路径的末端”。

递归访问每个结点n时,会将root到n的完整路径传入该函数。随后,这个函数会以相反的顺序,从n到root,将路径上的结点值加起来。当每条子路径的总和等于sum时,就打印这条路径。

public static void findSum(TreeNode node, int sum) {
        int depth = depth(node);
        int[] path = new int[depth];
        findSum(node, sum, path, 0);
    }
    //求树的深度
    public static int depth(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            return Math.max(depth(node.left), depth(node.right)) + 1;
        }
    }
    public static void findSum(TreeNode node, int sum, int[] path, int level) {
        if (node == null) {
            return;
        }
        path[level] = node.data;//将当前结点插入路径
        //从当前结点到root查找以此为终点的且总和为sum的路径
        int t = 0;
        for (int i = level; i >= 0; i--) {
            t += path[i];
            if (t == sum) {
                print(path, i, level);
            }
        }
        //查找当前结点之下的结点
        findSum(node.left, sum, path, level + 1);
        findSum(node.right, sum, path, level + 1);
        path[level] = Integer.MIN_VALUE;
    }
    public static void print(int[] path, int start, int end) {
        for (int i = start; i <= end; i++) {
            System.out.print(path[i] + " ");
        }
        System.out.println();
    }
View Code

时间复杂度为O(nlogn),空间复杂度为O(logn)。

原文地址:https://www.cnblogs.com/struggleli/p/7852439.html