Skip to main content

101. Symmetric Tree

分析

Traversal Possibilities Starting at the root of a binary tree, there are three main steps that can be performed and the order in which they are performed defines the traversal type. These steps are: performing an action on the current node (referred to as “visiting” the node and it is denoted with “D”), traversing to the left child (denoted with “L”) traversing to the right child node (denoted with “R”). This process can be easily described through recursion. Based on the above definition there are 6 possibilities:

  1. LDR : Process left sub-tree -> Process the current node -> Process right sub-tree
  2. LRD: Process left sub-tree -> Process right sub-tree -> Process the current node
  3. DLR: Process the current node -> Process left sub-tree -> Process right sub-tree
  4. DRL: Process the current node -> Process right sub-tree -> Process left sub-tree
  5. RDL: Process right sub-tree -> Process the current node -> Process left sub-tree
  6. RLD: Process right sub-tree -> Process left sub-tree -> Process the current node
挺好玩的题目,同时用两种方式遍历一棵树

题解

function isSymmetric(root: TreeNode | null): boolean {
if (!root) {
return true
}

const dfs = (nodeUseDLR: TreeNode | null, nodeUseDRL: TreeNode | null) => {
if (nodeUseDLR === null && nodeUseDRL === null) {
return true
}
if (nodeUseDLR === null || nodeUseDRL === null) {
return false
}
if (nodeUseDLR.val !== nodeUseDRL.val) {
return false
}
return dfs(nodeUseDLR.left, nodeUseDRL.right) && dfs(nodeUseDLR.right, nodeUseDRL.left)
}

return dfs(root, root)
}