Leetcode 235:二叉搜索树的最近公共祖先(最详细的解法!!!)

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5] 1234567 _______6______ / \ ___2__ ___8__/ \ / \0 _4 7 9 / \ 3 5 示例 1: 123输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例 2: 123输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4输出: 2解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。 说明: 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉搜索树中。

阅读全文

Leetcode 437:路径总和 III(最详细的解法!!!)

给定一个二叉树,它的每个结点都存放着一个整数值。 找出路径和等于给定数值的路径总数。 路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。 二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。 示例: 123456789101112131415root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \3 -2 1返回 3。和等于 8 的路径有:1. 5 -> 32. 5 -> 2 -> 13. -3 -> 11

阅读全文

Leetcode 129:二叉树的所有路径(最详细的解法!!!)

给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。 例如,从根到叶子节点路径 1->2->3 代表数字 123。 计算从根到叶子节点生成的所有数字之和。 说明: 叶子节点是指没有子节点的节点。 示例 1: 123456789输入: [1,2,3] 1 / \ 2 3输出: 25解释:从根到叶子节点路径 1->2 代表数字 12.从根到叶子节点路径 1->3 代表数字 13.因此,数字总和 = 12 + 13 = 25. 示例 2: 123456789101112输入: [4,9,0,5,1] 4 / \ 9 0 / \5 1输出: 1026解释:从根到叶子节点路径 4->9->5 代表数字 495.从根到叶子节点路径 4->9->1 代表数字 491.从根到叶子节点路径 4->0 代表数字 40.因此,数字总和 = 495 + 491 + 40 = 1026.

阅读全文

Leetcode 112:路径总和(最详细的解法!!!)

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例:给定如下二叉树,以及目标和 sum = 22, 1234567 5 / \ 4 8 / / \ 11 13 4 / \ \7 2 1 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

阅读全文

Leetcode 222:完全二叉树的节点个数(最详细的解法!!!)

给出一个完全二叉树,求出该树的节点个数。 说明: 完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。 示例: 12345678输入: 1 / \ 2 3 / \ /4 5 6输出: 6

阅读全文

Leetcode 110:平衡二叉树(最详细的解法!!!)

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

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

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回 true
示例 2:

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

1
2
3
4
5
6
7
      1
/ \
2 2
/ \
3 3
/ \
4 4

返回 false

解题思路

对于这个问题,我们可以非常快的写出递归版本。当root为空的时候,我们将None也看成是一棵二叉树,所以返回True。接着我们判断左子树高度右子树高度差是不是大于1,如果是,那么我们返回False就好啦。如果不是接着递归判断左子树右子树是不是一棵平衡二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:        
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True

def height(node):
if not node:
return 0

return max(height(node.left), height(node.right)) + 1

if abs(height(root.left) - height(root.right)) > 1:
return False

return self.isBalanced(root.left) and self.isBalanced(root.right)

但是如你所见,这个解法有一个很明显的弊端,就是我们在每次求height的时候有大量的重复运算,我们怎么可以避免这种重复运算呢?或者说我们有什么办法在遍历一遍树(求一次height)的过程中就可以得到答案呢?我们希望当左右子树中存在不平衡的时候就可以提前停止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:        
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def height(node):
if not node:
return 0

left = height(node.left)
right = height(node.right)
if left == -1 or right == -1 or abs(left - right) > 1:
return -1

return max(left, right) + 1

return height(root) != -1

上面这种解法非常的巧妙,当树出现不平衡的时候,我们令树的高度是-1

同样的,对于可以用递归解决的问题,我们都应该思考一下怎么可以通过迭代去解决。那这个问题怎么通过迭代解决呢?我们可以先通过BFS得到一个list,然后从list的最后一个节点回退到root,并且计算节点的深度差,更新各节点深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:        
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
nodes = [root]
for node in nodes:
if node:
nodes.extend([node.left, node.right])

depths = {}
nodes.reverse()
for node in nodes:
if node:
if abs(depths.get(node.left, 0) - depths.get(node.right, 0)) > 1:
return False

depths[node] = max(depths.get(node.left, 0), depths.get(node.right, 0)) + 1

return True

我们也可以通过前序遍历的方式去更新节点的深度。但是这里的问题和之前的Leetcode 144:二叉树的前序遍历(最优雅的解法!!!)中有一些区别,之前的问题中是输出节点,而我们这里是要更新节点。所以我们不能直接将节点弹出,而是要保留到更新完节点后再弹出。这要怎么做呢?我们可以通过建立一个tuple包含一个seen信息,表示这个节点之前是不是访问过。如果访问过我们再将节点弹出,否则的话再将节点插回去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:        
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
stack = list()
stack.append((root, 0))
depths = {}
while stack:
node, seen = stack.pop()
if node:
if not seen:
stack.extend([(node, 1), (node.right, 0), (node.left, 0)])
if abs(depths.get(node.left,0) - depths.get(node.right,0)) > 1:
return False
depths[node] = max(depths.get(node.left,0), depths.get(node.right,0)) + 1

return True

依照这种思路,我们也可以写出中序遍历后序遍历的版本。这个问题还没有结束,它还能延伸出这样的问题:如何判断完全二叉树?如何判断满二叉树?我们由前面的问题 Leetcode 222:完全二叉树的节点个数(最详细的解法!!!)知道了完全二叉树的定义

在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

递归实现:

我们知道这样的两个性质,如果我们将root.index0开始计算的话

  • 左孩子=2*i + 1
  • 右孩子=2*i + 2

基于这个性质,我们可以先计算节点的个树,然后每个节点的index是不是>=len(tree),如果是的话,那么自然就返回False,直到所有节点都访问完。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:  
def _isCompleteBT(self, root, index, num):
if not root:
return True

if index >= num:
return False
return self._isCompleteBT(root.left, index*2 + 1, num) and self._isCompleteBT(root.left, index*2 + 2, num)

def isCompleteBT(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def countNodes(node):
if not node:
return 0
return 1+ countNodes(node.left) + countNodes(node.right)

num = countNodes(root)
return self._isCompleteBT(root, 0, num)

迭代实现:

我们可以通过BSF遍历整棵二叉树,对于每个节点我们要做这样的判断

  • 左孩子为空,右孩子也必须为空
  • 左右孩子都为空或者左孩子不为空而右孩子为空,那么接下来要遍历的节点都必须是叶子节点
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
class Solution:        
def isCompleteBT(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True

queue = [root]
flag = False
while queue:
node = queue.pop(0)
if node.left:
if flag:
return False
queue.append(node.left)
else:
flag = True

if node.right:
if flag:
return False
queue.append(node.right)
else:
flag = True

return True

如何判断满二叉树呢?

递归实现:

主要分成这样几种情况:

  • root空,True
  • root非空,root.leftroot.right都为空,True
  • root非空,root.leftroot.right都不为空,递归下去
  • root非空,root.left为空root.right不为空,root.left不为空root.right为空,False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:        
def isFullBT(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True

if not root.left and not root.right:
return True

if root.left and root.right:
return self.isFullBT(root.left) and self.isFullBT(root.right)

return False

递归实现:

计算树的节点个数num_nodes和树的深度depth。然后通过depth计算出节点数,比较二者是否想同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:        
def isFullBT(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def countNodes(node):
if not node:
return 0
return 1+ countNodes(node.left) + countNodes(node.right)

def height(node):
if not node:
return 0
return max(height(node.left), height(node.right)) + 1

num_nodes = countNodes(root)
depth = height(root)
return True if 2**depth - 1 == num_nodes else False

至此,这个问题告一段落了。一个Easy的问题,不知不觉就被我们展开成了一个不小的问题QAQ。。。。但是

我们能否将heightcountNodes合并到一块去呢?这似乎是一个有意思的问题。好吧,就这样吧!!!大家可以想一想。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!