victory的博客

长安一片月，万户捣衣声

0%

发表于 更新于 分类于 ， ， ，

111.二叉树的最小深度

题目描述

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

题目链接

思路

方法一：深度优先搜索
首先可以想到使用深度优先搜索的方法，遍历整棵树，记录最小深度。
对于每一个非叶子节点，我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题。
方法二：广度优先搜索
使用广度优先搜索的方法，遍历整棵树。
当我们找到一个叶子节点时，直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。

代码

# Definition for a binary tree node.
import collections


class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def minDepth(self, root):
        """
        深度优先搜索
        :type root: TreeNode
        :rtype: int
        """
        def get_depth(root):
            if root is None:
                return 0
            left_depth = get_depth(root.right)
            right_depth = get_depth(root.left)
            return min(right_depth, left_depth) + 1

        return get_depth(root)

    def minDepth1(self, root):
        """深度优先搜索"""
        if not root:
            return 0

        if not root.left and not root.right:
            return 1

        min_depth = 10 ** 9
        if root.left:
            min_depth = min(self.minDepth1(root.left), min_depth)
        if root.right:
            min_depth = min(self.minDepth1(root.right), min_depth)
        return min_depth + 1

    def minDepth2(self, root):
        """深度优先搜索"""
        if not root:
            return 0

        que = collections.deque([(root, 1)])
        while que:
            node, depth = que.popleft()
            if not node.left and not node.right:
                return depth
            if node.left:
                que.append((node.left, depth + 1))
            if node.right:
                que.append((node.right, depth + 1))

        return 0

    def create_binary_tree(self, nodes_list):
        node1 = TreeNode(nodes_list[1])
        node3 = TreeNode(nodes_list[3])
        node4 = TreeNode(nodes_list[4])
        node2 = TreeNode(nodes_list[2], node3, node4)
        root = TreeNode(nodes_list[0], node1, node2)
        return root


if __name__ == "__main__":
    slt = Solution()
    root = slt.create_binary_tree([3, 9, 20, 15, 7])
    print(slt.minDepth(root))

发表于 分类于 ， ， ，

分页

实现功能：
当我们点击首页菜单栏的商品类别链接时，显示该分类下一定数量的商品，当该分类的总商品数大于这个数量，就会由几页数据，此时我们再点击页码时浏览器显示对应页的商品。
实现分页功能需要的数据：

数据 获取/计算方式
当前页展示的数据(List) select * from product limit (当前页-1)*每页显示几条 每页显示几条
每页显示几条数据 自定义
当前页 从前台传递
总页数 总条数/每页显示多少条
总条数 使用count关键字 select count(*) form product

header.jsp
修改属性class=”nav navbar-nav”的ul下面的菜单栏代码

<%@ page language="java" contentType="text/html; charset=UTF-8"
    pageEncoding="UTF-8"%>
<%@taglib prefix="c" uri="http://java.sun.com/jsp/jstl/core"%>
<!DOCTYPE html>
<!-- 登录 注册 购物车... -->
<div class="container-fluid">
    <div class="col-md-4">
        <img src="img/logo2.png" />
    </div>
    <div class="col-md-5">
        <img src="img/header.png" />
    </div>
    <div class="col-md-3" style="padding-top:20px">
        <ol class="list-inline">
            <c:if test="${empty user}">
                <li><a href="login.jsp">登录</a></li>
                <li><a href="register.jsp">注册</a></li>
            </c:if>
            <c:if test="${not empty user}">
                <li>${user.username}</li>
                <li><a href="cart.jsp">购物车</a></li>
                <li><a href="order_list.jsp">我的订单</a></li>
            </c:if>
        </ol>
    </div>
</div>

<!-- 导航条 -->
<div class="container-fluid">
    <nav class="navbar navbar-inverse">
        <div class="container-fluid">
            <!-- Brand and toggle get grouped for better mobile display -->
            <div class="navbar-header">
                <button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#bs-example-navbar-collapse-1" aria-expanded="false">
                    <span class="sr-only">Toggle navigation</span>
                    <span class="icon-bar"></span>
                    <span class="icon-bar"></span>
                    <span class="icon-bar"></span>
                </button>
                <a class="navbar-brand" href="#">首页</a>
            </div>

            <div class="collapse navbar-collapse" id="bs-example-navbar-collapse-1">
                <ul class="nav navbar-nav">
                    <c:forEach items="${clist}" var="cate">
                        <li><a href="${pageContext.request.contextPath}/product?method=findListByCate&cid=${cate.cid}&pageNumber=1">${cate.cname}</a></li>
                    </c:forEach>
                </ul>
                <form class="navbar-form navbar-right" role="search">
                    <div class="form-group">
                        <input type="text" class="form-control" placeholder="Search">
                    </div>
                    <button type="submit" class="btn btn-default">Submit</button>
                </form>
            </div>
        </div>
    </nav>
</div>

product_list.jsp
修改分页部分的代码

<%@ page language="java" contentType="text/html; charset=UTF-8"
    pageEncoding="UTF-8"%>
<%@taglib prefix="c" uri="http://java.sun.com/jsp/jstl/core" %>
<!DOCTYPE html>
<html>
<head>
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>会员登录</title>
<link rel="stylesheet" href="css/bootstrap.min.css" type="text/css" />
<script src="js/jquery-1.11.3.min.js" type="text/javascript"></script>
<script src="js/bootstrap.min.js" type="text/javascript"></script>
<!-- 引入自定义css文件 style.css -->
<link rel="stylesheet" href="css/style.css" type="text/css" />

<style>
body {
    margin-top: 20px;
    margin: 0 auto;
    width: 100%;
}

.carousel-inner .item img {
    width: 100%;
    height: 300px;
}
</style>
</head>

<body>


    <!-- 引入header.jsp -->
    <jsp:include page="/header.jsp"></jsp:include>


    <div class="row" style="width: 1210px; margin: 0 auto;">
        
        <c:forEach items="${pb.list}" var="pro">
            <div class="col-md-2">
                <a href="${pageContext.request.contextPath}/product?method=getProById&pid=${pro.pid}"> 
                    <img src="${pageContext.request.contextPath}/${pro.pimage}" width="170" height="170" style="display: inline-block;">
                </a>
                <p>
                    <a href="product_info.html" style='color: green'>${pro.pname}</a>
                </p>
                <p>
                    <font color="#FF0000">商城价：&yen;${pro.shop_price}</font>
                </p>
            </div>
        </c:forEach>
    </div>

    <!--分页 -->
    <div style="width: 380px; margin: 0 auto; margin-top: 50px;">
        <ul class="pagination" style="text-align: center; margin-top: 10px;">
            <li class="disabled"><a href="#" aria-label="Previous"><span
                    aria-hidden="true">&laquo;</span></a></li>
            <c:forEach begin="1" end="${pb.totalCount}" step="1" var="n">
                <li><a href="${pageContext.request.contextPath}/product?method=findListByCate&cid=${cid}&pageNumber=${n}">${n}</a></li>
            </c:forEach>
            <li><a href="#" aria-label="Next"> <span aria-hidden="true">&raquo;</span>
            </a></li>
        </ul>
    </div>
    <!-- 分页结束 -->



    <!-- 引入footer.jsp -->
    <jsp:include page="/footer.jsp"></jsp:include>

</body>

</html>

PageBean.java

package com.oracle.bean;

import java.util.ArrayList;
import java.util.List;

public class PageBean {
    private List<Product> list = new ArrayList<>();//显示当前页数据 select * form product limit
    private int pageSize;//每页显示几条数据 自定义
    private int pageNumber;//当前页 从前台传递过来
    private int totalCount;//(int)Math.ceil(totalSize*1.0/pageSize)
    private int totalSize;//总条数 select count(*) form product
    public List<Product> getList() {
        return list;
    }
    public void setList(List<Product> list) {
        this.list = list;
    }
    public int getPageSize() {
        return pageSize;
    }
    public void setPageSize(int pageSize) {
        this.pageSize = pageSize;
    }
    public int getPageNumber() {
        return pageNumber;
    }
    public void setPageNumber(int pageNumber) {
        this.pageNumber = pageNumber;
    }
    public int getTotalCount() {
        return (int)Math.ceil(totalSize*1.0/pageSize);
    }
    public void setTotalCount(int totalCount) {
        this.totalCount = totalCount;
    }
    public int getTotalSize() {
        return totalSize;
    }
    public void setTotalSize(int totalSize) {
        this.totalSize = totalSize;
    }
    
    //获取index索引的方法
    public int getIndex() {
        return (pageNumber-1)*pageSize;
    }
    public PageBean(int pageSize, int pageNumber) {
        super();
        this.pageSize = pageSize;
        this.pageNumber = pageNumber;
    }
}

ProductServlet.java
变更ProductServlet.java中的findListByCate方法代码如下：

public void findListByCate(HttpServletRequest request, HttpServletResponse response) {
        // TODO Auto-generated method stub
        try {
            String pn = request.getParameter("pageNumber");
            int pageNumber = Integer.parseInt(pn);
            int pageSize = 4;
            
            String cid = request.getParameter("cid");
            ProductService ps = new ProductService();
            
            //List<Product> plist = ps.findListByCate(cid);
            PageBean pb = ps.findListByCate(cid, pageNumber, pageSize);
            
            request.setAttribute("cid", cid);
            request.setAttribute("pb", pb);
            request.getRequestDispatcher("/product_list.jsp").forward(request, response);
        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        
}

ProductService.java
变更ProductService.java中的findListByCate方法代码如下：

public PageBean findListByCate(String cid, int pageNumber, int pageSize) throws SQLException {
        // TODO Auto-generated method stub
        ProductDao pd = new ProductDao();
        //List<Product> plist = pd.findListByCate(cid);
        
        //查询每页显示的数据
        List<Product> plist = pd.findListByCate(cid, pageNumber, pageSize);
        
        //查询总条数
        int count = pd.getCount(cid);
        PageBean pb = new PageBean(pageSize, pageNumber);
        pb.setList(plist);
        pb.setTotalSize(count);
        
        return pb;
    }

ProductDao.java
修改ProductDao.java中的findListByCate方法代码并添加getCount方法如下：

public List<Product> findListByCate(String cid, int pageNumber, int pageSize) throws SQLException {
    // TODO Auto-generated method stub
    QueryRunner qr = new QueryRunner(DataSourceUtils.getDataSource());
    
    PageBean pb = new PageBean(pageSize, pageNumber);
    
    String sql = "select * from product where cid=? and pflag=? order by pdate desc limit ?,?";
    
    List<Product> plist = qr.query(sql, new BeanListHandler<>(Product.class), cid, 0, pb.getIndex(), pb.getPageSize());
    return plist;
}

public int getCount(String cid) throws SQLException {
    // TODO Auto-generated method stub
    QueryRunner qr = new QueryRunner(DataSourceUtils.getDataSource());
    
    String sql = "select count(*) from product where cid=?";
    
    int count = ((Long) qr.query(sql, new ScalarHandler(), cid)).intValue();
    return count;
}