Tino又想吃肉了

对称二叉树

Note swift algorithm leetcode
Word count: 314Reading time: 1 min
2021/03/16

判断对称二叉树的两种解法

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/
2 2
/ \ /
3 4 4 3

[[1],[2,2],[3,4,4,3]]

其中，二叉树节点定义为：

1
2
3
4
5
6
7
8
9
10
11
12
 class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    func isSymmetric(_ root: TreeNode?) -> Bool {
        return DFC(root?.left,root?.right)
    }
    func DFC(_ lhs:TreeNode?,_ rhs:TreeNode?) -> Bool{
        if lhs == nil && rhs == nil{
            return true
        }

        if lhs?.val != rhs?.val {
            return false
        }

        return DFC(lhs?.left,rhs?.right) && DFC(lhs?.right,rhs?.left)
    }
}

迭代解法

  • 在这里只记录思路
  • 通过一次对二叉树的遍历，将二叉树所有的左节点和右节点分别存到两个队列里，然后比较两个队列的元素是否相等。注意：要从头节点的子节点开始，因为头节点在对称二叉树的判断中无意义

Tino Wu

CATALOG
  1. 1. 给定一个二叉树，检查它是否是镜像对称的。
Total : 35
2022
2021
swift iOS Tools algorithm leetcode tree 动态规划 计网 DFS算法 双指针 排序 BFS 性能优化 底层原理 操作系统 启动流程
Note