31.树

# 01.树的遍历

# 0、生成树结构

1.前序遍历： DBACEGF（根节点排最先，然后同级先左后右）
2.中序遍历： ABCDEFG (先左后根最后右）
3.后序遍历： ACBFGED （先左后右最后根）

# 1、python

#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
    def __init__(self,value=None,left=None,right=None):
        self.value=value
        self.left=left    #左子树
        self.right=right  #右子树

if __name__=='__main__':
    root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))

1
2
3
4
5
6
7
8
9
10

# 2、golang

package main

import "fmt"

type TreeNode struct {
	Val    string
    Left   *TreeNode  // 左子树
    Right  *TreeNode  // 右子树
}

func main() {
	root := TreeNode{
		Val: "D",
		Left: &TreeNode{
			Val: "B",
			Left: &TreeNode{
				Val: "A",
			},
			Right: &TreeNode{
				Val: "C",
			},
		},
		Right: &TreeNode{
			Val: "E",
			Right: &TreeNode{
				Val: "G",
				Left: &TreeNode{
					Val: "F",
				},
			},
		},
	}
	fmt.Println(root)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 1、先根遍历

144.二叉树的前序遍历 (opens new window)

# 1、python

前序遍历： DBACEGF（根节点排最先，然后同级先左后右）

#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
    def __init__(self,value=None,left=None,right=None):
        self.value=value
        self.left=left    #左子树
        self.right=right  #右子树

def preTraverse(root):
     '''
     前序遍历
     '''
     if root==None:
         return
     print(root.value)  # 打印当前根节点的值
     preTraverse(root.left)  # 只要有左孩子就一直递归
     preTraverse(root.right)

if __name__=='__main__':
    root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
    print('前序遍历：')
    preTraverse(root)   #  DBACEGF

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

先根遍历步骤推演

1
2
3
4
5

#步骤 1: dfs(4) 打印4
#步骤 2: dfs(2) 打印2
#步骤 3: dfs(1) 打印1
左子树 dfs(None) 返回
右子树 dfs(None) 返回

#步骤 4: 返回到节点 2，继续遍历右子树
#步骤 5: 进入节点 3
dfs(right) = dfs(3) 打印3
左子树 dfs(None) 返回
右子树 dfs(None) 返回
#步骤 6: 返回到节点 2
节点 2: 完成对左子树和右子树的遍历，返回到节点 4

# 步骤 7: 返回到节点 4，继续遍历右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 2、golang

package main

import "fmt"

type TreeNode struct {
	Val    int
    Left   *TreeNode  // 左子树
    Right  *TreeNode  // 右子树
}

func preorderTraversal(root *TreeNode) []int {
	vals := []int{}  // 使用列表vals存放树中数据
	var preorder func(*TreeNode)
	preorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		vals = append(vals, node.Val)  // 将根节点值添加到列表中
		preorder(node.Left)         // 只要有左孩子就一直递归
		preorder(node.Right)
	}
	preorder(root)
	return vals

}

func main() {
	root := TreeNode{
		Val: 1,
		Right: &TreeNode{
			Val: 2,
			Left: &TreeNode{
				Val: 3,
			},
		},
	}
	vals := preorderTraversal(&root)
	fmt.Println(vals)  // [1 2 3]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# 2、中根遍历

94.二叉树的中序遍历 (opens new window)

# 1、python

ABCDEFG (先左后根最后右）

#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
    def __init__(self,value=None,left=None,right=None):
        self.value=value
        self.left=left    #左子树
        self.right=right  #右子树

def midTraverse(root):
    '''
    中序遍历
    '''
    if root == None:
        return
    midTraverse(root.left)  # 只要有左孩子就一直递归（这样第一个打印的就是最左边的孩子）
    print(root.value)
    midTraverse(root.right)

if __name__=='__main__':
    root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
    print('中序遍历：')
    midTraverse(root)   #  ABCDEFG  (先左后根最后右）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

中根遍历步骤推演

1
2
3
4
5

#步骤 1: dfs(4) 
#步骤 2: 递归 dfs(2)
#步骤 3: 递归 dfs(1)
左子树 dfs(None) 返回
打印1
右子树 dfs(None) 返回

#步骤 4: 返回到节点 2，继续遍历右子树
打印2
递归遍历右子树 (节点 3)

#步骤 5: 进入节点 3  dfs(3) 
左子树 dfs(None) 返回
打印3
右子树 dfs(None) 返回

#步骤 6: 返回到节点 2
节点 2: 完成对左子树和右子树的遍历，返回到节点 4

# 步骤 7: 返回到节点 4，继续遍历右子树
打印4
递归遍历右子树 (节点 6)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 2、golang

package main

import "fmt"

type TreeNode struct {
	Val    int
    Left   *TreeNode  // 左子树
    Right  *TreeNode  // 右子树
}

func inorderTraversal(root *TreeNode) (res []int) {
	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		inorder(node.Left)  //  只要有左孩子就一直递归（这样第一个打印的就是最左边的孩子）
		res = append(res, node.Val)
		inorder(node.Right)
	}
	inorder(root)
	return
}

func main() {
	root := TreeNode{
		Val: 1,
		Right: &TreeNode{
			Val: 2,
			Left: &TreeNode{
				Val: 3,
			},
		},
	}
	vals := inorderTraversal(&root)
	fmt.Println(vals)  // [1 3 2]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 3、后根遍历

# 1、python

后序遍历： ACBFGED （先左后右最后根）

#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
    def __init__(self,value=None,left=None,right=None):
        self.value=value
        self.left=left    #左子树
        self.right=right  #右子树

def afterTraverse(root):
    '''
    后序遍历
    '''
    if root == None:
        return
    afterTraverse(root.left)  # 只要有左孩子就一直递归
    afterTraverse(root.right)
    print(root.value)

if __name__=='__main__':
    root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
    print('后序遍历：')
    afterTraverse(root)   #  ACBFGED

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 2、golang

package main

import "fmt"

type TreeNode struct {
	Val    int
    Left   *TreeNode  // 左子树
    Right  *TreeNode  // 右子树
}

func postorderTraversal(root *TreeNode) (res []int) {
	var postorder func(*TreeNode)
	postorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		postorder(node.Left)  // 只要有左孩子就一直递归
		postorder(node.Right)
		res = append(res, node.Val)
	}
	postorder(root)
	return
}

func main() {
	root := TreeNode{
		Val: 1,
		Right: &TreeNode{
			Val: 2,
			Left: &TreeNode{
				Val: 3,
			},
		},
	}
	vals := postorderTraversal(&root)
	fmt.Println(vals)  // [3 2 1]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 4、分层打印二叉树

# 1、python

#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left  # 左子树
        self.right = right  # 右子树

def layer(root):
    curLayer = [root]  # 当前层的节点
    while curLayer:    # 只要当前层有节点就循环
        layerValue = []   # 当前层节点对应的值
        nextLayer = []    # 下一层节点
        for node in curLayer:  # 循环当前节点
            layerValue.append(node.value)  # 添加当前层节点的值
            if node.left:
                nextLayer.append(node.left)  # 添加下一层节点左节点
            if node.right:
                nextLayer.append(node.right)  # 添加下一层节点右节点
        print(layerValue)  # 打印当前层的值
        curLayer = nextLayer  # 移动到下一层


if __name__ == '__main__':
    root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
    layer(root)

'''
['D']
['B', 'E']
['A', 'C', 'G']
['F']
'''

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 2、golang

package main

import (
	"fmt"
)

type TreeNode struct {
	Val    int
    Left   *TreeNode  // 左子树
    Right  *TreeNode  // 右子树
}

func levelOrderBottom(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	vals := [][]int{}
	curLayer := []*TreeNode{root}    // 当前层的节点
	for len(curLayer) > 0 {          // 只要当前层有节点就循环
		layerValue := []int{}        // 当前层节点对应的值
		nextLayer := []*TreeNode{}   // 下一层节点
		for _, node := range curLayer {      // 循环当前节点
			layerValue = append(layerValue, node.Val)  // 添加当前层节点的值
			if node.Left != nil {
				nextLayer = append(nextLayer, node.Left)   // 添加下一层节点左节点
			}
			if node.Right != nil {
				nextLayer = append(nextLayer, node.Right)  // 添加下一层节点右节点
			}
		}
		curLayer = nextLayer   // 移动到下一层
		vals = append([][]int{layerValue}, vals...)  // 将当前层追加到列表头部
	}
	return vals
}

func main() {
	root := TreeNode{
		Val: 3,
		Left: &TreeNode{
			Val: 9,
		},
		Right: &TreeNode{
			Val: 20,
			Left: &TreeNode{
				Val: 15,
			},
			Right: &TreeNode{
				Val: 7,
			},
		},
	}
	vals := levelOrderBottom(&root)
	fmt.Println(vals)  // [[15,7],[9,20],[3]]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

# 02.广度优先BFS

D B E A C G F

# 1、python栈实现

#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left  # 左子树
        self.right = right  # 右子树

# 广度优先搜索
def bfs(root):
    res = []
    q = [root] # 先把根节点放进队列中
    while q:  # 当队列不为空时进入循环体
        current_node = q.pop(0)  # 取出队列的第一个节点
        print(current_node.value)
        if current_node.left:   # 如果左子树不为空，就加入队列
            q.append(current_node.left)
        if current_node.right:  # 如果右子树不为空，就加入队列
            q.append(current_node.right)
    return res

if __name__ == '__main__':
    root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
    bfs(root)  # D B E A C G F

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 2、python分层

#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left  # 左子树
        self.right = right  # 右子树

def bfs(root):
    curLayer = [root]  # 当前层的节点
    while curLayer:    # 只要当前层有节点就循环
        nextLayer = []    # 下一层节点
        for node in curLayer:  # 循环当前节点
            print(node.value)
            if node.left:
                nextLayer.append(node.left)  # 添加下一层节点左节点
            if node.right:
                nextLayer.append(node.right)  # 添加下一层节点右节点
        curLayer = nextLayer  # 移动到下一层

if __name__ == '__main__':
    root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
    bfs(root)  # D B E A C G F

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 03.深度优先DFS

D B A C E G F

# 1、python栈实现

#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left  # 左子树
        self.right = right  # 右子树

# 深度优先搜索
def dfs(root):
    res = []
    q = [root]   # 先把根节点放进栈中
    while q:     # 当栈不为空时进入循环体
        current_node = q.pop()  # 取出栈顶节点
        print(current_node.value)
        if current_node.right:  # 如果右子树不为空，就压入栈
            q.append(current_node.right)
        if current_node.left:  # 如果左子树不为空，就压入栈
            q.append(current_node.left)
    return res

if __name__ == '__main__':
    root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
    dfs(root)  # D B A C E G F

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 2、python递归实现

#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left  # 左子树
        self.right = right  # 右子树

# 深度优先搜索
# 使用递归实现深度优先搜索
def dfs_recur(node):
    if not node: # 递归结束的条件是当该节点为None时
        return
    print(node.value)
    dfs_recur(node.left) # 对左子树进行递归
    dfs_recur(node.right) # 对右子树进行递归

if __name__ == '__main__':
    root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
    dfs_recur(root)  # D B A C E G F

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 04.路径总和

112.路径总和 (opens new window)
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum
判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum

输入：root = [1,2,3], targetSum = 5
输出：false

1
2

# 1、python

遍历二叉树，如果当前节点是叶子节点，检查路径总和是否等于 sum
否则，递归地在左右子树上继续检查，将当前节点的值从 sum 中减去

class ListNode:
	def __init__(self, val=None, left=None, right=None):
		self.val = val
		self.left = left  # 左子树
		self.right = right  # 右子树

def hasPathSum(root, sum):
	if not root:
		return False
	if not root.left and not root.right:
		return sum == root.val
	return hasPathSum(root.left, sum - int(root.val)) or hasPathSum(root.right, sum - int(root.val))

if __name__ == '__main__':
	root = ListNode(1, ListNode(2), ListNode(3))
	ret = hasPathSum(root, 3)
	print(ret)  # True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 05.二叉树直径

532.二叉树直径 (opens new window)
给定一棵二叉树，你需要计算它的直径长度
一棵二叉树的直径长度是任意两个结点路径长度中的最大值
这条路径可能穿过也可能不穿过根结点

1
2
3
4
5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]

# 1、python

对于每一个节点，我们计算它的左右子树深度之和来作为候选直径，同时全局比较更新
二叉树的直径是所有节点的左右子树深度之和中的最大值

class Solution:
    def diameterOfBinaryTree(self, root):
        self.res = 1
        def dfs(node):
            if not node:       # 访问到空节点了，返回0
                return 0
            L = dfs(node.left)        # 左儿子为根的子树的深度
            R = dfs(node.right)       # 右儿子为根的子树的深度
            self.res = max(self.res, L + R + 1)  # 计算d_node即L+R+1 并更新res
            return max(L, R) + 1      # 返回该节点为根的子树的深度
        dfs(root)
        return self.res - 1

1
2
3
4
5
6
7
8
9
10
11
12

# 06.二叉树最大深度

104.二叉树的最大深度 (opens new window)
给定一个二叉树，找出其最大深度
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数
下面这颗树最大深度为4

1
2
3
4
5
6
7

# 1、python

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数

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

def maxDepth(root):
	if root is None: return 0
	l = maxDepth(root.left)
	r = maxDepth(root.right)
	return max(l, r) + 1

if __name__ == '__main__':
	root = TreeNode(3,
					left=TreeNode(9),
					right=TreeNode(20, TreeNode(15), TreeNode(7, TreeNode(10)))
					)
	print(maxDepth(root))  # 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 07.二叉树的最小深度

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

输入：root = [3,9,20,null,null,15,7]
输出：2

1
2

# 1、python

如果当前节点的左右子树均为空，说明该节点是叶子节点，返回深度 1
如果左子树或右子树为空，我们需要返回存在子树的深度 + 1
如果左右子树都不为空，则递归计算左右子树的最小深度，并取最小值 + 1

class Solution:
    def minDepth(self, root):
        if not root: 
            return 0
        if not root.left and not root.right:
            return 1

        if not root.left:        # 如果左子树为空，返回右子树的最小深度 + 1
            return self.minDepth(root.right) + 1

        if not root.right:       # 如果右子树为空，返回左子树的最小深度 + 1
            return self.minDepth(root.left) + 1

        # 左右子树都存在，返回左右子树的最小深度 + 1
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 08.对称二叉树

101.对称二叉树 (opens new window)
给定一个二叉树，检查它是否是镜像对称的
例如，二叉树 [1,2,2,3,4,4,3] 是对称的

1
2
3
4
5

# 1、python

从树的根节点进行递归
递归结束有三种情况
- 第一：递归到两个节点都为空，证明前面的所有结果都是符合的，返回True
- 第二：递归过程中，有对称的两个节点值不相同，返回False
- 得三：递归到最后，两个节点中有一个为空，那么也返回False

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

class Solution:
    def isSymmetric(self, root):
        def dfs(left, right):
            if not left and not right:  # 递归的终止条件是两个节点都为空
                return True
            if not (left and right):    # 或者两个节点中有一个为空
                return False
            if left.val != right.val:   # 或者两个节点的值不相等
                return False
            # dfs() and dfs()：的意思是只有and前面的dfs函数返回True才会执行后面dfs函数
            # dfs() or dfs()： 的意思是无论and前面的dfs执行结果是什么，都会执行后面的dfs
            return dfs(left.left, right.right) and dfs(left.right, right.left)

        return dfs(root.left, root.right)  # 用递归函数，比较左节点，右节点

if __name__ == '__main__':
    root = TreeNode(
        1,
        left=TreeNode(2,TreeNode(3),TreeNode(4)),
        right=TreeNode(2,TreeNode(4),TreeNode(3)),
    )
    print(Solution().isSymmetric(root))  # True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 09.有序数组转换为二叉搜索树

108.将有序数组转换为二叉搜索树 (opens new window)
给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵二叉搜索树
二叉搜索树定义：
- 平衡: 高度差小于或等于 1
- 搜索树: 左子树值小于n，右子树值都大于n

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

1
2
3

# 1、python

二叉搜索树的中序遍历是升序序列，因此可以确保数组是二叉搜索树的中序遍历序列
总是选择中间位置左边的数字作为根节点，根节点的下标为mid=(left+right)//2

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

class Solution:
    def sortedArrayToBST(self, nums):
        def helper(left, right):
            if left > right:
                return None
            mid = (left + right) // 2  # 总是选择中间位置左边的数字作为根节点

            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root
        return helper(0, len(nums) - 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 10.平衡二叉树

# 110.平衡二叉树 (opens new window)
给定一个二叉树，判断它是否是高度平衡的二叉树
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1

# 1、python

对于当前遍历到的节点，首先计算左右子树的高度
如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点
并判断左子树和右子树是否平衡
这是一个自顶向下的递归的过程

class Solution:
    def isBalanced(self, root):
        def dfs(node):        # 计算树的高度
            if not node:
                return 0
            l = dfs(node.left)
            r = dfs(node.right)
            return max(l, r) + 1

        if not root:         # 如果根节点为空，则树是平衡的（空树是平衡的）
            return True

        l = dfs(root.left)                      # 计算当前根节点的左右子树高度差
        r = dfs(root.right)
        return (abs(l - r) <= 1 and                # 判断左右子树的高度差是否小于等于 1
                self.isBalanced(root.left) and     # 并且递归判断左子树和右子树是否平衡
                self.isBalanced(root.right))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 11.从前序与中序遍历序列构造二叉树

105.从前序与中序遍历序列构造二叉树 (opens new window)
给定两个整数数组 preorder 和 inorder ，请构造二叉树并返回其根节点
其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
构造的二叉树应表示为：[3, 9, 20, null, null, 15, 7]

1
2
3

# 1、python

先序遍历：先跟后左最后右

中序遍历：先左后根最后右

初始化时，将先序遍历的第一个元素作为根节点，并压入栈中
因为 中序列表中第一个元素就是树的最左叶子节点
所以遍历先序列表，当val相等时证明先序遍历到达了最左叶子节点
此时弹出栈中节点同步移动中序遍历指针，找到val不相等的节点，这个节点就是右子树的节点
把右节点放到对应子树根节点的 right，直到先序遍历的所有val全部都处理完成

这个方法的时间复杂度是 O(n)，因为每个节点只访问一次，空间复杂度是 O(n)，因为最坏情况下栈的深度可能达到 n

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

class Solution:
    def buildTree(self, preorder, inorder):
        if not preorder:          # 若先序遍历为空，返回 None
            return None
        
        root = TreeNode(preorder[0])       # 先序遍历的第一个元素是根节点
        stack = [root]                     # 用于构建树的节点栈
        idx = 0                            # 中序遍历的索引

        for i in range(1, len(preorder)):  # 从第二个元素开始，逐个处理先序遍历
            preVal = preorder[i]
            node = stack[-1]

            # 如果当前栈顶节点不等于中序遍历的当前值，说明要处理左子树
            if node.val != inorder[idx]:
                node.left = TreeNode(preVal)
                stack.append(node.left)
            else:
                # 如果相等，表示当前节点构建完毕，继续处理右子树
                while stack and stack[-1].val == inorder[idx]:
                    node = stack.pop()
                    idx += 1
                node.right = TreeNode(preVal)
                stack.append(node.right)

        return root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 12.二叉树的右视图

199.二叉树的右视图 (opens new window)
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

1
2
3
4
5
6
7
8
9

# 1、python

我们可以对二叉树进行层次遍历，那么对于每层来说，最右边的结点一定是最后被遍历到的
二叉树的层次遍历可以用广度优先搜索实现

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

class Solution:
    def rightSideView(self, root):
        if root is None:
            return []
        ret = []
        curLayer = [root]             # 当前层的节点
        while curLayer:               # 只要当前层有节点就循环
            layerValue = []           # 当前层节点对应的值
            nextLayer = []            # 下一层节点
            for node in curLayer:     # 循环当前节点
                layerValue.append(node.val)        # 添加当前层节点的值
                if node.left:
                    nextLayer.append(node.left)    # 添加下一层节点左节点
                if node.right:
                    nextLayer.append(node.right)   # 添加下一层节点右节点
            # 每层只获取最右节点即可
            ret.append(layerValue[-1])
            curLayer = nextLayer                   # 移动到下一层
        return ret


if __name__ == '__main__':
    root = TreeNode(1, left=TreeNode(2, right=TreeNode(5)), right=TreeNode(3, left=TreeNode(4)))
    print(Solution().rightSideView(root))  # [1, 3, 4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 13.二叉树的锯齿形层序遍历

103.二叉树的锯齿形层序遍历 (opens new window)
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历
即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行

    3
   / \
  9  20
    /  \
   15   7

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

1
2
3
4
5
6
7
8

# 1、python

和广度优先遍历相似，is_l2r变量标记从左向右遍历
每层遍历一层后进行取反，is_l2r=false 否反转当前层的结果即可

class Solution:
    def zigzaglayerValueOrder(self, root):
        if not root:             # 如果树为空，则直接返回空列表
            return []

        res = []                 # 用于存储最终的锯齿形层序遍历结果
        curLayer = [root]        # 使用列表作为队列，初始时包含根节点
        is_l2r = True            # 标记当前层的遍历方向，初始为从左到右

        while curLayer:
            layerValue = []      # 用于暂存当前层的节点值
            nextLayer = []       # 用于存储下一层的节点

            for node in curLayer:
                layerValue.append(node.val)  # 将节点值添加到当前层的结果中
                if node.left:                # 将当前节点的子节点添加到下一层的队列中
                    nextLayer.append(node.left)
                if node.right:
                    nextLayer.append(node.right)

            if not is_l2r:                  # 根据当前层的遍历方向决定是否反转当前层的结果
                layerValue.reverse()

            res.append(layerValue)          # 将当前层的结果添加到最终结果中
            curLayer = nextLayer            # 更新队列为下一层的节点
            is_l2r = not is_l2r             # 切换遍历方向

        return res                          # 返回最终的锯齿形层序遍历结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 14.二叉树的最近公共祖先

236.二叉树的最近公共祖先 (opens new window)
“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大
一个节点也可以是它自己的祖先

# 1、python

递归终止条件：
- 如果当前节点为空，返回 None，表示该路径上没有找到目标节点
- 如果当前节点是 p 或 q，直接返回当前节点，因为已经找到了目标节点
返回结果：
- 如果左右子树都找到祖先，则当前节点就是 p 和 q 的最近公共祖先
- 如果只在左子树或右子树找到一个祖先，则返回该祖先
- 如果左右子树都没有找到，则返回 None

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root:                 # 节点为空，返回 None
            return None
        if root == p or root == q:   # 如果当前节点就是 p 或 q 之一，则直接返回当前节点
            return root

        l = self.lowestCommonAncestor(root.l, p, q)      # 左子树查p、q最近公共祖先
        r = self.lowestCommonAncestor(root.r, p, q)      # 右子树查p、q公共祖先
        if l and r:           # 如果 p、q是当前节点左右叶子节点，当前节点就是最近公共祖先
            return root

        return l if l else r  # 找到左子树祖先返回，否则返回右子树祖先（左右子树都没有，返回 None）

1
2
3
4
5
6
7
8
9
10
11
12
13

# 15.二叉树中的最大路径和

124.二叉树中的最大路径和 (opens new window)
同一个节点在一条路径序列中 至多出现一次 ，该路径 至少包含一个 节点，且不一定经过根节点
路径和 是路径中各节点值的总和

# 1、python

对于每个节点，我们计算它的左子树和右子树的最大贡献值如果这些贡献值为负，则我们选择不包括这个子树（相当于贡献值为0）
对于每个节点来说，最大路径和可能是：
- 仅包含当前节点
- 包含当前节点和它的左子树
- 包含当前节点和它的右子树
- 包含当前节点、它的左子树和右子树

class Solution:
    def maxPathSum(self, root):
        self.max_sum = float('-inf')  # 初始化最大路径和为负无穷
        def dfs(node):
            if not node:
                return 0
            # 递归计算左右子树的最大贡献值
            l = max(dfs(node.left), 0)                   # 如果贡献值为负，取0
            r = max(dfs(node.right), 0)
            cur_max = node.val + l + r                   # 当前节点的最大路径和
            self.max_sum = max(self.max_sum, cur_max)    # 更新全局最大路径和
            return node.val + max(l, r)                  # 返回当前节点的最大贡献值
        dfs(root)
        return self.max_sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 16.求根节点到叶节点数字之和

129.求根节点到叶节点数字之和 (opens new window)
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字
每条从根节点到叶节点的路径都代表一个数字
计算从根节点到叶节点生成的 所有数字之和

# 1、python

在递归过程中，我们会累积从根节点到当前节点的路径所代表的数字
当到达叶节点时，就可以把这个累积的数字加到总和中

class Solution:
    def sumNumbers(self, root):
        def dfs(node, sum_):
            if not node:
                return 0
            sum_ = sum_ * 10 + node.val           # 更新路径上的当前数字
            if not node.left and not node.right:  # 如果是叶节点，直接返回当前路径所代表的数字
                return sum_
            l = dfs(node.left, sum_)
            r = dfs(node.right, sum_)
            return l + r                          # 返回左右子树的数字和的总和
        return dfs(root, 0)

1
2
3
4
5
6
7
8
9
10
11
12

推演

# dfs(4)  
sum_ = 0 * 10 + 4 = 4
# dfs(9)  
sum_ = 4 * 10 + 9 = 49
# dfs(5)  
sum_ = 49 * 10 + 5 = 495  # 此时 l = dfs(node.left, sum_) 返回=495

# 回溯到9执行 dfs(1) 
sum_ = 49 * 10 + 1 = 491  # 此时 r = dfs(node.right, sum_) 返回=491

# 回溯到9执行 return l + r
495+491=986

# 回溯到4     # 此时 l = dfs(node.left, sum_) 返回=986
dfs(0) 
sum_ = 4 * 10 + 0 = 40

# 回溯到4  
l = dfs(node.left, sum_) = 986
r = dfs(node.right, sum_) = 40
回溯到4执行 return l + r = 986 + 40 = 1026

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 17.验证二叉搜索树

98.验证二叉搜索树 (opens new window)
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树
二叉搜索树定义：左子树值小于n，右子树值都大于n

# 1、python

二叉搜索树定义：左子树值小于n，右子树值都大于n
遍历左子树：max_val=根节点 node.val不能大于根节点
遍历右子树：min_val=根节点 node.val不能小于根节点
只要有一个节点不满足情况就返回False，如果节点为空，证明是有效搜索树

class Solution:
    def isValidBST(self, root):
        def is_bst(node, min_val, max_val):
            if not node:                                      # 如果节点为空，返回True，表示当前子树是有效的BST
                return True

            # 遍历左子树：max_val=根节点 node.val不能大于根节点
            # 遍历右子树：min_val=根节点 node.val不能小于根节点
            if node.val <= min_val or node.val >= max_val:
                return False

            return (is_bst(node.left, min_val, node.val) and    # 遍历左子树  min_val=无穷小  max_val=根节点
                    is_bst(node.right, node.val, max_val))      # 遍历右子树  min_val=根节点  max_val=无穷大

        return is_bst(root, float("-inf"), float("inf"))         # 使用无穷小和无穷大作为初始值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 18.路径总和II

113.路径总和II (opens new window)
给你二叉树的根节点 root 和一个整数目标和 targetSum
找出所有从根节点到叶子节点路径总和等于给定目标和的路径

输入：root = [1,2,3], targetSum = 3
输出：[1, 2]

1
2

# 1、python 回溯

dfs 函数用于遍历树，并记录路径和
如果到达叶子节点且路径和等于目标值，将路径添加到 result 中
遍历左右子树，并在回溯时移除当前节点的值

class Solution:
    def pathSum(self, root, targetSum):
        res = []                            # 保存所有符合条件的路径
        def dfs(node, path, sum_):
            if not node:                    # 解决root本身为None的情况
                return
            
            path.append(node.val)           # 将当前节点的值添加到路径中
            sum_ += node.val                # 更新当前路径的节点值和

            # 如果当前节点是叶子节点，且路径和等于目标值，将当前路径加入结果
            if not node.left and not node.right and sum_ == targetSum:
                res.append(list(path))

            if node.left:
                dfs(node.left, path, sum_)

            if node.right:
                dfs(node.right, path, sum_)
            path.pop()
        dfs(root, [], 0)        # 从根节点开始深度优先搜索，初始路径为空，路径和为0
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 19.二叉树最大宽度

662.二叉树最大宽度 (opens new window)
给你一棵二叉树的根节点 root ，返回树的最大宽度
树的最大宽度 是所有层中最大的宽度

# 1、python

通过广度优先搜索，并记录每层节点的相对位置来计算每一层的宽度
节点的位置可以通过编号来表示，例如根节点的位置为0，左子节点的位置为 2*pos，右子节点的位置为 2*pos + 1
当前层宽度 = 当前层最后节点位置 - 当前层第一个节点位置 + 1

class Solution:
    def widthOfBinaryTree(self, root):
        if not root:
            return 0

        max_width = 0
        queue = [(root, 0)]  # 使用列表存储节点及其位置

        while queue:
            level_length = len(queue)
            _, first_pos = queue[0]  # 当前层第一个节点的位置
            for _ in range(level_length):
                node, pos = queue.pop(0)  # 取出队列的第一个节点
                # 将子节点加入队列并标记位置
                if node.left:
                    queue.append((node.left, 2 * pos))
                if node.right:
                    queue.append((node.right, 2 * pos + 1))
            # 当前层宽度 = 当前层最后节点位置 - 当前层第一个节点位置 + 1
            max_width = max(max_width, pos - first_pos + 1)

        return max_width

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 20.翻转二叉树

226.翻转二叉树 (opens new window)
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点

# 1、python

我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转
如果当前遍历到的节点 root 的左右两棵子树都已经翻转
那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转

class Solution:
    def invertTree(self, root):
        if not root: return root                 # 如果当前节点为空，直接返回
        left = self.invertTree(root.left)        # 递归翻转左子树
        right = self.invertTree(root.right)      # 递归翻转右子树
        
        root.left, root.right = right, left      # 交换当前节点的左右子树
        return root

1
2
3
4
5
6
7
8

# 21.二叉树的完全性检验

958.二叉树的完全性检验 (opens new window)
给你一棵二叉树的根节点 root ，请你判断这棵树是否是一棵 完全二叉树
在一棵 完全二叉树 (opens new window) 中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都尽可能靠左

输入：root = [1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，节点值为 {1} 和 {2,3} 的两层），且最后一层中的所有节点（{4,5,6}）尽可能靠左

1
2
3

# 1、python

对于给定节点，假设它的位置编号为 v
- 左子节点的位置编号为 2*v
- 右子节点的位置编号为 2*v + 1
我们使用 i指针记录当前节点索引位置
如果索引和队列长度一致，说明树是完全二叉树；否则不是

class Solution(object):
    def isCompleteTree(self, root):
        q = [(root, 1)]    # 1（假设根节点 索引=1）
        i = 0              # 使用i指针记录当前节点索引位置

        while i < len(q):               # i 还没有遍历到 q 列表的末，循环就会继续执行
            node, v = q[i]              # 取出当前节点及其编号
            i += 1                      # 移动到下一个节点
            if node:                    # 如果当前节点不为空
                q.append((node.left, 2*v))
                q.append((node.right, 2*v+1))

        return q[-1][1] == len(q)       # 最后编号等于总节点数，是完全二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13

# 22.二叉搜索树中第K小的元素

230.二叉搜索树中第K小的元素 (opens new window)
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）

# 1、python

在二叉搜索树中，中序遍历可以得到一个从小到大的有序序列
因此，第 k 小的元素就是中序遍历序列中的第 k 个元素

class Solution:
    def kthSmallest(self, root, k: int):
        self.cnt = 0              # 记录遍历了多少节点
        self.res = None           # 存储最终结果，即第 k 小的节点值

        def mid(node):
            # 如果当前节点为空，或者已经找到了结果，则终止递归
            if not node or self.res is not None:
                return
            mid(node.left)              # 递归遍历左子树
            self.cnt += 1               # 访问当前节点，将计数器加1
            if self.cnt == k:           # 如果计数器等于 k，说明当前节点就是第 k 小的节点
                self.res = node.val     # 记录结果
                return
            mid(node.right)             # 递归遍历右子树

        mid(root)                       # 中序遍历
        return self.res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 23.子结构判断

LCR 143.子结构判断 (opens new window)
给定两棵二叉树 tree1 和 tree2，判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值
注意，空树不会是以 tree1 的某个节点为根的子树具有 相同的结构和节点值

# 1、python

检查 A 和 B 是否匹配，或 B 是 A 左子树或右子树的子结构
如果 B 为 None，表示 B 已经全部匹配成功，因此返回 True
如果 A 为 None，但 B 还没有匹配完，或者 A.val != B.val，说明匹配失败，返回 False

class Solution:
    def isSubStructure(self, A, B):
        if not A or not B: return False      # A 和 B 都不为空才进行后续匹配
        
        def isSub(A, B):
            if not B:                        # 如果 B 为空，说明 B 已经遍历完了，匹配成功
                return True
            if not A or A.val != B.val:      # 如果 A 为空，或者 A 的值与 B 的值不相等，匹配失败
                return False
            return isSub(A.left, B.left) and isSub(A.right, B.right)    # 递归检查左右子树是否匹配

        # 然后检查 A 和 B 是否匹配，或 B 是 A 左子树或右子树的子结构
        return isSub(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)

1
2
3
4
5
6
7
8
9
10
11
12
13

# 24.另一棵树的子树

572.另一棵树的子树 (opens new window)
给你两棵二叉树 root 和 subRoot
检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树
如果存在，返回 true ；否则，返回 false

# 1、python

对于 root 树中的每一个节点，我们都检查以该节点为根的子树是否与 subRoot 树相同
如果发现了一个匹配的子树，我们就返回 true，否则继续检查其他节点

class Solution:
    def isSubtree(self, root, subRoot):
        if not root:                # 如果 root 为空但 subRoot 不为空，说明不是子树
            return False

        if not subRoot:             # 如果 subRoot 为空，任何树都有 subRoot 作为子树
            return True

        if self.isSame(root, subRoot):  # 如果当前节点是相同树，返回True
            return True

        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def isSame(self, A, B):           # 检查是否时相同树
        if not A and not B:           # 如果两棵树都找到None都没有找到不同的，证明子树相同
            return True
        if not A or not B or A.val != B.val:   # 如果其中一棵树为空或者值不同，说明不同
            return False
        l = self.isSame(A.left, B.left)
        r = self.isSame(A.right, B.right)
        return l and r                         # 如果左右子树都相同，则整棵树相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 25.将二叉搜索树转化为排序的双向链表

LCR 155.将二叉搜索树转化为排序的双向链表 (opens new window)
二叉搜索树定义：左子树值小于n，右子树值都大于n

输入：root = [2,1,3]
输出：[1,2,3]

1
2

# 1、python

节点应从小到大排序，因此应使用 中序遍历 “从小到大”访问树的节点
l指针记录左侧节点，r指针记录右侧节点(r比l多走一步)
对于每个节点r, 我们把r的左指针指向l，同时见l的右指针指向r
right指针指向下一个节点，left指针指向上一个节点

class Solution:
    def __init__(self):
        self.head = None           # 双向链表的头节点
        self.l = None              # 左指针记录双向链表中上一个节点（在 r 左侧）

    def treeToDoublyList(self, root):
        if root is None:
            return None

        self.dfs(root)                  # 执行深度优先搜索（DFS）遍历树并建立双向链表

        self.l.right = self.head        # 连接头节点和尾节点形成循环链表
        self.head.left = self.l
        return self.head

    def dfs(self, r):
        if r is None:
            return

        self.dfs(r.left)
        if self.l is None:          # l为空，证明首次调用，r赋值给链表的头节点
            self.head = r
        else:
            self.l.right = r       # 前一个右指针指向下一个节点r

        r.left = self.l            # 后一个左指针指向上一个节点（第一次l=None）
        self.l = r                 # 更新l指针（相当于向前移动一位）

        self.dfs(r.right)          # 递归处理右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

上次更新: 2024/9/11 16:38:01

← 21.链表 41.数学→

31.树

# 01.树的遍历

# 0、生成树结构

# 1、python

# 2、golang

# 1、先根遍历

# 1、python

# 2、golang

# 2、中根遍历

# 1、python

# 2、golang

# 3、后根遍历

# 1、python

# 2、golang

# 4、分层打印二叉树

# 1、python

# 2、golang

# 02.广度优先BFS

# 1、python栈实现

# 2、python分层

# 03.深度优先DFS

# 1、python栈实现

# 2、python递归实现

# 04.路径总和

# 1、python

# 05.二叉树直径

# 1、python

# 06.二叉树最大深度

# 1、python

# 07.二叉树的最小深度

# 1、python

# 08.对称二叉树

# 1、python

# 09.有序数组转换为二叉搜索树

# 1、python

# 10.平衡二叉树

# 110.平衡二叉树 (opens new window)

# 1、python

# 11.从前序与中序遍历序列构造二叉树

# 1、python

# 12.二叉树的右视图

# 1、python

# 13.二叉树的锯齿形层序遍历

# 1、python

# 14.二叉树的最近公共祖先

# 1、python

# 15.二叉树中的最大路径和

# 1、python

# 16.求根节点到叶节点数字之和

# 1、python

# 17.验证二叉搜索树

# 1、python

# 18.路径总和II

# 1、python 回溯

# 19.二叉树最大宽度

# 1、python

# 20.翻转二叉树

# 1、python

# 21.二叉树的完全性检验

# 1、python

# 22.二叉搜索树中第K小的元素

# 1、python

# 23.子结构判断

# 1、python

# 24.另一棵树的子树

# 1、python

# 25.将二叉搜索树转化为排序的双向链表

# 1、python