Fork me on GitHub

LeetCode-3.树-二

面试题 04.10. 检查子树

链接:https://leetcode-cn.com/problems/check-subtree-lcci/

检查子树。你有两棵非常大的二叉树:T1,有几万个节点;T2,有几万个节点。设计一个算法,判断 T2 是否为 T1 的子树。

如果 T1 有这么一个节点 n,其子树与 T2 一模一样,则 T2 为 T1 的子树,也就是说,从节点 n 处把树砍断,得到的树与 T2 完全相同。

示例1:

 输入:t1 = [1, 2, 3], t2 = [2]
 输出:true
示例2:

 输入:t1 = [1, null, 2, 4], t2 = [3, 2]
 输出:false
提示:

树的节点数目范围为[0, 20000]。

题解一:

一:在 t1 中找到 t2 的起点。先判断 t1 当前节点,如果不对就判断 t1 左子树和 t1 右子树。
二:从找到的起点开始判断剩下的点,t1 和 t2 同步左右子树搜索。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:

def helper(t1,t2):
if not t2:
return True
elif not t1 and t2:
return False
elif t1.val != t2.val:
return False
else:
return helper(t1.left,t2.left) and helper(t1.right,t2.right)

if not t1:
return False
if not t2:
return True
return helper(t1,t2) or self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:
if not t1:
return False
if not t2:
return True
return self.helper(t1,t2) or self.checkSubTree(t1.left,t2) or self.checkSubTree(t1.right,t2)

def helper(self,t1,t2):
if not t2:
return True
elif not t1 and t2:
return False
elif t1.val != t2.val:
return False
else:
return self.helper(t1.left,t2.left) and self.helper(t1.right,t2.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
if not A or not B:
return False
return self.helper(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)

def helper(self,A,B):
if not A and B:
return False
elif not B:
return True
elif A.val != B.val:
return False
else:
return self.helper(A.left,B.left) and self.helper(A.right,B.right)
1
2
3
4
5
6
7
8
9
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
def helper(A,B):
if not B:
return True
if not A or (A.val != B.val):
return False
return helper(A.left,B.left) and helper(A.right,B.right)
return bool(A and B) and (helper(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))

面试题 17.12. BiNode

链接:https://leetcode-cn.com/problems/binode-lcci/

二叉树数据结构TreeNode可用来表示单向链表(其中left置空,right为下一个链表节点)。实现一个方法,把二叉搜索树转换为单向链表,要求值的顺序保持不变,转换操作应是原址的,也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

注意:本题相对原题稍作改动

示例:

输入: [4,2,5,1,3,null,6,0]
输出: [0,null,1,null,2,null,3,null,4,null,5,null,6]
提示:

节点数量不会超过 100000。

题解一(迭代):

root.left=None
pre.right=root
pre=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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def convertBiNode(self, root: TreeNode) -> TreeNode:
head=TreeNode(0)
pre=head
stack=[]
while stack or root:
if root:
stack.append(root)
root=root.left
else:
root=stack.pop()

root.left=None
pre.right=root
pre=root

root=root.right
return head.right

题解二(递归):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def convertBiNode(self, root: TreeNode) -> TreeNode:
head=TreeNode(0)
self.helper(root,head)
return head.right

def helper(self,root,pre):
if root:
pre=self.helper(root.left,pre)
root.left=None
pre.right=root
pre=root
pre=self.helper(root.right,pre)
return pre

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def convertBiNode(self, root: TreeNode) -> TreeNode:
head=TreeNode(0)
self.pre=head
self.helper(root)
return head.right

def helper(self,root):
if not root:
return
self.helper(root.left)

root.left=None
self.pre.right=root
self.pre=root

self.helper(root.right)

面试题 04.12. 求和路径

链接:https://leetcode-cn.com/problems/paths-with-sum-lcci/

给定一棵二叉树,其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法,打印节点数值总和等于某个给定值的所有路径的数量。注意,路径不一定非得从二叉树的根节点或叶节点开始或结束,但是其方向必须向下(只能从父节点指向子节点方向)。

示例:
给定如下二叉树,以及目标和 sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

3
解释:和为 22 的路径有:[5,4,11,2], [5,8,4,5], [4,11,7]
提示:

节点总数 <= 10000

题解一(递归):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
if not root:
return 0
return self.helper(root,sum)+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)

def helper(self,root,sum):
count=0
if not root:
return 0
if sum-root.val==0:
count+=1
count+=self.helper(root.left,sum-root.val)
count+=self.helper(root.right,sum-root.val)
return count

面试题54. 二叉搜索树的第k大节点

链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

给定一棵二叉搜索树,请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

限制:

1 ≤ k ≤ 二叉搜索树元素个数

题解一(迭代):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
if not root:
return 0
stack=[]
while stack or root:
if root:
stack.append(root)
root=root.right
else:
root=stack.pop()
k-=1
if k==0:
return root.val
root=root.left

题解二(递归):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
self.k=k
self.res=0
self.helper(root)
return self.res
def helper(self,root):
if not root:
return 0
self.helper(root.right)
if self.k==0: return # 提高性能,提前返回。
self.k-=1
if self.k==0:
self.res=root.val # 直接return不行,需要存入全局变量中
self.helper(root.left)
return self.res

面试题55 - I. 二叉树的深度

链接:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/

输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。

例如:

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

提示:节点总数 <= 10000

题解一(递归):

1
2
3
4
5
6
7
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
left=self.maxDepth(root.left)
right=self.maxDepth(root.right)
return max(left,right)+1

题解二(迭代):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
stack=[root]
depth=0
while stack:
tmp=[]
for i in range(len(stack)):
root=stack.pop()
if root.left:
tmp.append(root.left)
if root.right:
tmp.append(root.right)
stack=tmp
depth+=1
return depth

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
stack=[root]
depth=0
while stack:
tmp=[]
for root in stack:
if root.left:
tmp.append(root.left)
if root.right:
tmp.append(root.right)
stack=tmp
depth+=1
return depth

面试题55 - II. 平衡二叉树

链接:https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

限制:1 <= 树的结点个数 <= 10000

题解一(递归):

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if not root:
return True
return abs(self.helper(root.left)-self.helper(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

def helper(self,root):
if not root:
return 0
left=self.helper(root.left)
right=self.helper(root.right)
return max(left,right)+1

面试题68 - I. 二叉搜索树的最近公共祖先

链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。


说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

最近公共祖先(最近公共节点):

根据题目给定的前提:

    所有节点的值都是唯一的。
    p、q 为不同节点且均存在于给定的二叉搜索树中。

说明有以下几种情况:

    二叉树本身为空,root == null ,return root
    p.val == q.val ,一个节点也可以是它自己的祖先
    p.val 和 q.val 都小于 root.val
    (两个子节点的值都小于根节点的值,说明它们的公共节点只能在二叉树的左子树寻找)
    p.val 和 q.val 都大于 root.val
    (两个子节点的值都大于根节点的值,说明它们的公共节点只能在二叉树的右子树寻找)
    如果上述的情况皆不满足,说明其公共节点既不在左子树也不在右子树上,只能为最顶端的公共节点,return root
    p.val < root.val && q.val > root.val 或 p.val > root.val && q.val < root.val

题解一(递归):

1
2
3
4
5
6
7
8
9
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# if not root:
# return
if root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right,p,q)
elif root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left,p,q)
return root

题解二(后序遍历):

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root==p or root==q:
return root
l=self.lowestCommonAncestor(root.left,p,q)
r=self.lowestCommonAncestor(root.right,p,q)
if not l:
return r
elif not r:
return l
else:
return root

题解三(迭代):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if root.val < p.val and root.val < q.val:
root=root.right
elif root.val > p.val and root.val > q.val:
root=root.left
else:
break
return root

面试题68 - II. 二叉树的最近公共祖先

链接:https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。


说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

题解一(后序遍历):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root or root==p or root==q:
return root
l=self.lowestCommonAncestor(root.left,p,q)
r=self.lowestCommonAncestor(root.right,p,q)
if not l:
return r
elif not r:
return l
else:
return root

支持,让我的文章更加优秀!