110. Balanced Binary Tree
https://leetcode.com/problems/balanced-binary-tree/description/
要判断树是否平衡，根据题目的定义，深度是必须的信息，所以我们必须维护深度，另一方面我们又要返回是否为平衡树，那么对于左右子树深度差的判断也是必要的。这里我们用一个整数来做返回值，而0或者正数用来表示树的深度，而-1则用来表示此树已经不平衡了，如果已经不平衡，则递归一直返回-1即可，也没有继续比较的必要了，否则就利用返回的深度信息看看左右子树是不是违反平衡条件，如果违反返回-1，否则返回左右子树深度大的加一作为自己的深度即可。算法的时间复杂度是一次树的遍历O(n)，空间是栈高度O(logn)。可以看出树的题目万变不离其宗，都是递归遍历，只是处理保存量，递归条件和结束条件会有一些变化。
代码如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.getHeight(root) != -1
def getHeight(self, root):
if not root:
return 0
leftHeight = self.getHeight(root.left)
if leftHeight == -1:
return -1
rightHeight = self.getHeight(root.right)
if rightHeight == -1:
return -1
if abs(leftHeight - rightHeight) > 1:
return -1
return max(leftHeight, rightHeight) + 1
做题时的感悟:
leftHeight = self.getHeight(root.left)
if leftHeight == -1:
return -1
rightHeight = self.getHeight(root.right)
if rightHeight == -1:
return -1
我们在得到left之后，应当立即判断left是否为-1，如果是说明左面已经不平衡了，可以直接返回-1，不需要再判断右面了。可以提高算法的效率。
100. Same Tree
https://leetcode.com/problems/same-tree/description/
这道题是树的题目，属于最基本的树遍历的问题。这里我们主要考虑一下结束条件，如果两个结点都是None，也就是到头了，那么返回True。如果其中一个是None，说明在一棵树上结点到头，另一棵树结点还没结束，即树不相同，或者两个结点都非空，并且结点值不相同，返回False。最后递归处理两个结点的左右子树，返回左右子树递归的与结果即可。这里使用的是先序遍历，算法的复杂度跟遍历是一致的，如果使用递归，时间复杂度是O(n)，空间复杂度是O(logn)。
树的题目大多都是用递归来完成比较简练，当然也可以如同Binary Tree Inorder Traversal中介绍的那样，用非递归方法甚至线索二叉树来做，只需要根据要求做相应改变即可。
代码如下：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
101. Symmetric Tree
https://leetcode.com/problems/symmetric-tree/description/
本质上还是树的遍历，也就是里面的程序框架加上对称性质的判断即可。主要说说结束条件，假设到了某一结点，不对称的条件有以下三个：
（1）左边为空而右边不为空；
（2）左边不为空而右边为空；
（3）左边值不等于右边值。
根据这几个条件在遍历时进行判断即可。算法的时间复杂度是树的遍历O(n)，空间复杂度同样与树遍历相同是O(logn)。
递归代码如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# Solution 1 - Recursion
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
return self.helper(root.left, root.right)
def helper(self, p, q):
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return self.helper(p.left, q.right) and self.helper(p.right, q.left)
非递归方法是使用层序遍历来判断对称性质。非递归方法比起递归方法要繁琐一些，因为递归可以根据当前状态（比如两个都为空）直接放回true，而非递归则需要对false的情况一一判断，不能如递归那样简练。
迭代代码如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# Solution 2 - Iteration
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
queue = [(root.left, root.right)]
while queue:
p, q = queue.pop()
if not p and not q:
continue
if not p or not q:
return False
if p.val != q.val:
return False
else:
queue.append((p.left, q.right))
queue.append((p.right, q.left))
# queue.insert(0, (p.left, q.right))
# queue.insert(0, (p.right, q.left))
return True
网友评论