递归法，判断二叉树是否为镜像对称。
镜像特点：
- 根节点：左节点值 = 右节点值
- 非根节点：左节点值 = 兄弟节点的右节点值
因此，可对每两个镜像节点做如下判断：
if 节点A为空:
if 节点B为空:
return 是镜像
else:
return 不是镜像
else:
if 节点B为空:
return 不是镜像
else:
if 节点A值 == 节点B值:
return 是镜像
else:
return 不是镜像
对接下来的节点进行递归：
- A节点的左节点与B节点的右节点
- A节点的右节点与B节点的左节点
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root is None:
return True
else:
return self.checkElement(root.left, root.right)
def checkElement(self, left_root, right_root):
if left_root is None or right_root is None:
return left_root == right_root
if left_root.val != right_root.val:
return False
return self.checkElement(left_root.left, right_root.right) and self.checkElement(left_root.right, right_root.left)/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
return symmetric(root.Left, root.Right)
}
func symmetric(left *TreeNode, right *TreeNode) bool {
if left == nil || right == nil {
return left == right
}
if left.Val != right.Val {
return false
}
return symmetric(left.Left, right.Right) && symmetric(left.Right, right.Left)
}# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if root is None:
return True
queue = []
queue.append(root.left)
queue.append(root.right)
while len(queue) > 0:
left = queue[0]
del queue[0]
right = queue[0]
del queue[0]
if left is None:
if right is None:
pass
else:
return False
else:
if right is None:
return False
else:
queue.append(left.left)
queue.append(right.right)
queue.append(left.right)
queue.append(right.left)
if left.val != right.val:
return False
return True/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSymmetric(root *TreeNode) bool {
queue := make([]*TreeNode, 0)
if root == nil {
return true
}
queue = append(queue, root.Left)
queue = append(queue, root.Right)
for len(queue) > 0 {
left := queue[0]
queue = queue[1:]
right := queue[0]
queue = queue[1:]
if left == nil {
if right != nil {
return false
}
} else {
if right == nil {
return false
} else {
queue = append(queue, left.Left)
queue = append(queue, right.Right)
queue = append(queue, left.Right)
queue = append(queue, right.Left)
if left.Val != right.Val {
return false
}
}
}
}
return true
}树的路径问题，使用递归。
- 对左右节点调用递归函数，分别得到：
- 左节点相同值路径
- 右节点相同值路径
- 同值路径计算：
- 左节点存在且与当前节点值相同，left++；不同：left=0
- 右节点存在且与当前节点值相同，right++；不同：right=0
- 结果
result = max(result, left + right)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
max_length = 0
def longestUnivaluePath(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
self.getMaxLen(root, root.val)
return self.max_length
def getMaxLen(self, root, val):
if not root:
return 0
left = self.getMaxLen(root.left, root.val)
right = self.getMaxLen(root.right, root.val)
if root.left and root.left.val == root.val:
left = left + 1
else:
left = 0
if root.right and root.right.val == root.val:
right = right + 1
else:
right = 0
self.max_length = max(self.max_length, left + right)
# 选择较大路径值与 parent 相连
return max(left, right)