(面试)打印二叉树的所有最右节点--python

系统 545 0

       打印二叉树最右侧节点其实是改自二叉树的层次遍历,多了一步,即输出每一层的末尾节点。如下题,输出最右侧节点结果应为 [3,20,7]。

(面试)打印二叉树的所有最右节点--python_第1张图片

首先看二叉树的层次遍历,使用队列(queue)来存储二叉树的节点,

(面试)打印二叉树的所有最右节点--python_第2张图片    (面试)打印二叉树的所有最右节点--python_第3张图片    

(面试)打印二叉树的所有最右节点--python_第4张图片

具体代码层次遍历实现:

            
              def levelOrder(self, root: TreeNode) -> List[List[int]]:
        list = []
        if root is None:return list
        queue = [root]
        while queue:
            cur = []
            for i in range(len(queue)):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                cur.append(node.val)
            list.append(cur)
        return list
            
          

 打印出二叉树最右侧节点:

            
                  # 打印二叉树最右节点
    def printRightNode(self, root):
        queue = [root]
        list = []
        while queue:
            res = []
            # 控制二叉树每层的节点
            for i in range(len(queue)):
                node = queue.pop(0)
                if node.lchild:
                    queue.append(node.lchild)
                if node.rchild:
                    queue.append(node.rchild)
                res.append(node.key)
            list.append(res)
        ans = []
        for i in list:
            # 取每层最后一个节点即为最右节点
            ans.append(i[-1])
        print(ans)
            
          

 


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请请扫描上面二维码支持博主1元、2元、5元等您想捐的金额吧,狠狠点击下面给点支持吧

发表我的评论
最新评论 总共0条评论