爬楼梯-二叉树

微信公众号：三木小小推^[1]
系列：刷题之Python
如果你觉得该系列对你有帮助，欢迎点好看^[2]

问题描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：
输入：2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶

2. 2 阶
   示例 2：
   输入：3
   输出：3
   解释：有三种方法可以爬到楼顶。

3. 1 阶 + 1 阶 + 1 阶

4. 1 阶 + 2 阶

5. 2 阶 + 1 阶

题目分析

二叉树遍历，可采用递归或堆栈形式，可剪枝
主要学习了二叉树及其堆栈遍历，明天在此基础解决问题

class Tree(object):
    """树类"""
    def __init__(self):
        self.root = Node()
        self.myQueue = []
        self.count = 0
    def add(self, elem):
        """为树添加节点"""
        node = Node(elem)
        if self.root.elem == -1:  # 如果树是空的，则对根节点赋值
            self.root = node
            self.myQueue.append(self.root)
        else:
            treeNode = self.myQueue[0]  # 此结点的子树还没有齐。
            if treeNode.lchild == None:
                treeNode.lchild = node
                self.myQueue.append(treeNode.lchild)
            else:
                treeNode.rchild = node
                self.myQueue.append(treeNode.rchild)
                self.myQueue.pop(0)  # 如果该结点存在右子树，将此结点丢弃。

        def front_stack(self, root, n):
        """利用堆栈实现树的先序遍历"""
        if root == None:
            return
        myStack = []
        node = root
        while node or myStack:
            while node:                     #从根节点开始，一直找它的左子树
                myStack.append(node)
                if sum(myStack) == n:
                    self.count += 1
                node = node.lchild
            node = myStack.pop()            #while结束表示当前节点node为空，即前一个节点没有左子树了
            node = node.rchild                  #开始查看它的右子树

欢迎订阅

下面是三木小小推的二维码，欢迎订阅呦~~

你点的每个好看，我都认真当成了喜欢