Li Kai

  • 主页
  • 所有文章
文章分类 友情链接 关于我

Li Kai

  • 主页
  • 所有文章

算法(六)二叉树

2018-09-20

本文简单介绍一下二叉树的遍历以及二叉树的相关题目。

1. 二叉树的遍历

1.1 前序遍历

根节点->左子树->右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#递归实现
#没有返回值的递归
def traversal(node, result):
if not node:
return
result.add(node.val)
traversal(node.left, result)
traversal(node.right, result)

#分治实现
#分而治之,带返回值的递归
def preorderTraversal(node):
result = []
if not node:
return result
left = preorderTraversal(node.left)
right = preorderTraversal(node.right)
result.append(root.val)
result += left
result += right
return result

1.2 中序遍历

左子树->根节点->右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 递归不带返回值
def traversal(node, result):
if not node:
return
traversal(node.left, result)
result.add(node.val)
traversal(node.right, result)

# 分治算法
def middleTraversal(node):
result = []
if not node:
return result
left = middleTraversal(node.left)
result += left
result.append(node.val)
right = middleTraversal(node.right)
result += right
return result

1.3 后序遍历

左子树->右子树->根节点

1
2
3
4
5
6
def traversal(node, result):
if not node:
return
traversal(node.left, result)
traversal(node.right, result)
result.add(node.val)

1.4 非递归实现二叉搜索数的遍历

非递归就是栈的实现,用栈来模拟递归调用, 参考文档https://juejin.cn/post/6844903503807119374

  1. 先序遍历
    不需要入栈,每次遍历到“左”节点,立即输出即可。

需要注意的是,遍历到最左下的节点时,实际上输出的已经不再是实际的根节点,而是实际的左节点。这符合先序的定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
def preorderTraversal(node):
res, stack = [], []
if not root: return res

cur = root
while stack or cur:
while cur:
res.append(cur.val)
stack.append(cur)
cur = cur.left
top = stack.pop()
#转向
cur = top.right
  1. 中序遍历
    基于对先序的分析,先序与中序的区别只在于对“左”节点的处理上,我们调整一行代码即可完成中序遍历。注意,我们在出栈之后才访问这个节点。因为先序先访问实际根,后访问实际左,而中序恰好相反。相同的是,访问完根+左子树(先序)或左子树+根(中序)后,都需要转向到“右”节点,使“右”节点称为新的“左”节点。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def inorderTraversal(node):
    res, stack = [], []

    if not root: return res

    cur = root
    while stack or cur:
    while cur:
    stack.append(cur)
    cur = cur.left
    top = stack.pop()
    res.append(top.val)
    cur = top.left
  2. 后序遍历
    后序遍历是左右中,按照中右左入栈,然后逆序就可以。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def postorderTraversal(node):
    res, stack = [], []

    if not root: return res

    cur = root
    while stack or cur:
    while cur:
    res.append(cur.val)
    stack.append(cur)
    cur = cur.right
    top = stack.pop()
    cur = top.left

    return res[::-1]
    方法二:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    def postorderTraversal(self, root):
    res, stack = [], []

    if not root: return res

    cur = root
    prev = None

    while cur or stack:
    while cur:
    stack.append(cur)
    cur = cur.left
    top = stack.pop()
    if not top.right or top.right == prev:
    res.append(top.val)
    prev = top
    cur = None
    else:
    stack.append(top)
    cur = top.right

    return res

    2.运用递归解决树的问题

递归分为”自底向上”,”自顶向下”的递归

2.1 自顶向下的递归

自顶向下的递归,就是记录经过的path,继续执行下一个step,下面是一个自顶向下求解二叉树深度的例子

1
2
3
4
5
6
7
def max_depth(node, depth):
if not node:
return
if not node.left and not node.right:
max_depth = max(max_depth, depth)
max_depth(node.left, depth +1)
max_depth(node.right, depth +1)

2.2 自底向上的递归

自底向上是带返回值的递归

1
2
3
4
5
6
def max_depth(node):
if not node:
return 0
left = max_depth(node.left)
right = max_depth(node.right)
return max(left, right) +1

3. 二叉树相关题

3.1 最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
分治思想
"""
def LCA(root, p1, p2):
if not root:
return None
if root == p1 or root == p2:
return root

left = LCA(root.left, p1, p2)
right = LCA(root.right, p1, p2)

#表明p1和p2分别在left和right子树,所以root就是最近公共祖先
if left and right:
return root
#表明p1,p2都在左子树,所以left就是最近公共祖先
if left:
return left
#表明p1,p2都在又子树,所以right就是最近公共祖先
if right:
return right

3.2 二叉树root到叶子节点的最大和

1
2
3
4
5
6
7
def maxPath(root):
if not root:
return 0

left = self.maxPath(root.left)
right = self.maxPath(root.right)
return max(left, right) + root.val

3.3 二叉树root到任意节点的最大和

1
2
3
4
5
6
7
8
def maxPath(root):
if not root:
return 0

left = self.maxPath(root.left)
right = self.maxPath(root.right)
#如果子树和小于0,还不如不要
return max(0, left, right) + root.val

3.4 二叉树任意节点到任意节点的最大和

两个分治
首先讨论情况,主要分三种,

  1. 垮root节点路径在root的两边
    该类问题结果就是 max(root.left to any的最大值, 0) + max(root.right to any 的最大值, 0 )+ root.val
  2. 路径全在左子树: 递归调用即可
  3. 路径全在由子树: 递归调用即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def maxPathAny2Any(node):

#加缓存节省时间
@lru_cache(None)
def maxPathRoot2Any(node):
if not node:
return 0
left = maxPathRoot2Any(node.left)
right = maxPathRoot2Any(node.right)
return max(left, right, 0) + node.val

# 因为至少有1个节点,所以返回最小值
if not node:
return -float("inf")

# 如果小于0,我还不如不要
left2any = max(maxPathRoot2Any(node.left), 0)
right2any = max(maxPathRoot2Any(node.right), 0)

# 比较垮root,全在左子树,全在右子树的情况,取最大值
return max(left2any+right2any+node.val, maxPathAny2Any(node.left), maxPathAny2Any(node.right))
  • 算法

扫一扫,分享到微信

微信分享二维码
算法(七)并查集
算法(五)回溯
  1. 1. 1. 二叉树的遍历
    1. 1.1. 1.1 前序遍历
    2. 1.2. 1.2 中序遍历
    3. 1.3. 1.3 后序遍历
    4. 1.4. 1.4 非递归实现二叉搜索数的遍历
  2. 2. 2.运用递归解决树的问题
    1. 2.1. 2.1 自顶向下的递归
    2. 2.2. 2.2 自底向上的递归
  3. 3. 3. 二叉树相关题
    1. 3.1. 3.1 最近公共祖先
  4. 4. 3.2 二叉树root到叶子节点的最大和
  5. 5. 3.3 二叉树root到任意节点的最大和
  6. 6. 3.4 二叉树任意节点到任意节点的最大和
收藏文章
登录
表情删除后不可恢复,是否删除
取消
确定
图片正在上传,请稍后...
取消上传
评论内容为空!
还没有评论,快来抢沙发吧!
  • 最新评论
该评论已关闭!
likai博客正在使用畅言云评
去社区看看吧
去热评看看吧
  • 手把手教你如何用golang实现一个timewheel时间轮 | LiKai的博客
    手把手教你如何用golang实现一个timewheel时间轮 | LiKai的博客
  • 数据结构-队列 | LiKai的博客
    数据结构-队列 | LiKai的博客
  • 算法(五)回溯 | LiKai的博客
    算法(五)回溯 | LiKai的博客
  • Python高级用法 | LiKai的博客
    Python高级用法 | LiKai的博客
  • 手把手教你如何用golang实现一个timewheel时间轮 | LiKai的博客
  • 数据结构-队列 | LiKai的博客
  • 算法(五)回溯 | LiKai的博客
  • Python高级用法 | LiKai的博客
热评话题
  • Python高级用法 | LiKai的博客
  • SQL基础教程(四) | LiKai的博客
  • Golang高级教程(一)for-range, switch, select使用 | LiKai的博客
  • 算法(二)深度优先搜索DFS | LiKai的博客
  • 算法(三)二分查找 | LiKai的博客
  • Golang高级教程(二)类型断言 | LiKai的博客
  • 算法(八)最短路径 | LiKai的博客
关闭
按钮 内容不能为空!
立刻说两句吧! 查看0条评论
  • 你收到0条新通知
  • 你有0条评论收到赞同
  • 你有0条新回复
  • 本日畅言云评热评新鲜出炉啦!
  • 你有0个任务已完成
  • 你收获0个畅言云评足迹
© 2021 Li Kai
Hexo Theme Yilia by Litten
  • 文章分类
  • 友情链接
  • 关于我

tag:

  • test
  • 数据结构
  • shell
  • 计算机网络
  • 数据库
  • 负载均衡
  • ovn
  • 算法
  • linux
  • kubernetes
  • sql
  • python
  • openstack
  • designate
  • neutron
  • golang
  • timewheel

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录(注意不是yilia根目录)执行以下命令:
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置:

      jsonContent:
        meta: false
        pages: false
        posts:
          title: true
          date: true
          path: true
          text: false
          raw: false
          content: false
          slug: false
          updated: false
          comments: false
          link: false
          permalink: false
          excerpt: false
          categories: false
          tags: true
    

  • 手把手教你如何用golang实现一个timewheel时间轮

    2021-04-04

    #算法#golang#timewheel

  • Golang线程池实现百万级高并发

    2021-03-21

    #golang

  • 基于ECMP的多活负载均衡策略

    2020-12-12

    #负载均衡

  • neutron metadata 服务详解

    2020-10-11

    #openstack#neutron

  • ovn为外部主机提供dhcp服务

    2020-09-20

    #ovn

  • Neutron网络troubleshooting

    2020-09-09

    #openstack#neutron

  • kubernetes中pod的自动伸缩

    2020-04-05

    #kubernetes

  • Golang高级教程(二)类型断言

    2020-02-04

    #golang

  • Golang高级教程(一)for-range, switch, select使用

    2020-02-02

    #golang

  • Kubernetes容器安全之Apparmor

    2020-01-04

    #kubernetes

  • 网络性能测试

    2019-09-19

    #计算机网络

  • 算法(十一)刷题常用语法python/go

    2019-07-18

    #算法#python#golang

  • 算法(十)快速排序

    2019-07-10

    #算法#python#golang

  • 算法(九)记忆化搜索

    2019-06-08

    #算法

  • linux常用指令

    2019-03-31

    #linux

  • OpenStack Designate简介

    2019-03-03

    #openstack#designate

  • 算法(八)最短路径

    2018-12-09

    #算法

  • 算法(七)并查集

    2018-10-21

    #算法

  • 算法(六)二叉树

    2018-09-19

    #算法

  • 算法(五)回溯

    2018-07-19

    #算法

  • Python yield使用

    2018-07-09

    #python

  • 算法(四)前缀和

    2018-07-05

    #算法

  • 算法(三)二分查找

    2018-05-19

    #算法

  • 算法(二)深度优先搜索DFS

    2018-04-20

    #算法

  • Python装饰器

    2018-04-19

    #python

  • Python高级用法

    2018-04-09

    #python

  • 算法(一)单调栈

    2018-03-19

    #算法

  • Python单例模式

    2018-03-08

    #python

  • Python编程规范

    2017-05-09

    #python

  • SQL基础教程(四)

    2017-04-19

    #数据库#sql

  • SQL基础教程(三)

    2017-04-11

    #数据库#sql

  • SQL基础教程(二)

    2017-03-24

    #数据库#sql

  • SQL基础教程(一)

    2017-03-19

    #数据库#sql

  • 9.计算机网络-QOS

    2016-08-19

    #计算机网络

  • 8.计算机网络-网络安全(下)

    2016-08-08

    #计算机网络

  • 7.计算机网络-网络安全(上)

    2016-08-01

    #计算机网络

  • 6.计算机网络-应用层

    2016-07-27

    #计算机网络

  • 5.计算机网络-传输层

    2016-07-24

    #计算机网络

  • 4.计算机网络-网络层

    2016-07-22

    #计算机网络

  • 3.计算机网络-数据链路层

    2016-07-17

    #计算机网络

  • 2.计算机网络-物理层

    2016-07-14

    #计算机网络

  • 1.计算机网络概述

    2016-07-09

    #计算机网络

  • Hash算法实现之MD5

    2016-04-09

    #算法

  • 数据结构-链表

    2016-04-02

    #数据结构

  • 数据结构-队列

    2016-04-01

    #数据结构

  • 数据结构-栈

    2016-03-31

    #数据结构

  • Shell基础

    2016-03-27

    #shell

  • Hello World

    2016-03-24

    #test

  • 我的博客园
  • 我的CSDN1
  • 我的CSDN2
李凯
研究生毕业于北邮
现就职于腾讯

一名奋斗在
OpenStack(Python)
Kubernetes(Golang)
的搬运工