算法练习-判断二叉树是否对称

gistfile1.txt

/*
对称二叉树树
     1
   /   \
  2     2
 / \   / \
4   8 8   4
*/
// 对称二叉树树
var symmetricTree = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
    },
    right: {
      val: 8
    }
  },
  right: {
    val: 2,
    left: {
      val: 8,
    },
    right: {
      val: 4,
    }
  }
}
/*
非对称二叉树树
     1
   /   \
  2     2
 / \   /
4   8 8
*/
// 非对称二叉树树
var notSymmetricTree = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
    },
    right: {
      val: 8
    }
  },
  right: {
    val: 2,
    left: {
      val: 8,
    },
  }
}
// 递归实现
function isSymmetricTreeRecursive(root) {
  // 树为空返回true
  if (!root) return true;
  // 返回他们的对称性
  return isSymmetric(root.left, root.right);
}

// 迭代实现
function isSymmetricTreeIterative(root) {
  if (!root) return true;
  var stack = []; // 定义一个辅助栈
  // 根节点的左右子树入栈
  stack.unshift(root.left);
  stack.unshift(root.right);
  // 栈不为空一直执行操作
  while (stack.length) {
    var s = stack.shift(), t = stack.shift();
    if (!s && !t) continue; // 都为空继续执行操作
    if (!s || !t) return false; // 一个为空一个不为空肯定不对称
    if (s.val != t.val) return false; // 如果两个节点值不同，则不对称
    
    stack.unshift(s.left); // 左左子树 对 右右子树
    stack.unshift(t.right); 
    stack.unshift(s.right); // 左右子数 对 右左子树
    stack.unshift(t.left);
  }
  return true;
}

// 对比两颗二叉树是否对称
function isSymmetric(s, t) {
  // s t 树都存在时判断
  if (s && t) {
    return s.val === t.val && // 当前节点值是否相等
        // 左节点的左子树 和 右节点的右子树是否相等
        // 左节点的右子树 和 右节点的左子树是否相等
        isSymmetric(s.left, t.right) && isSymmetric(s.right, t.left);
  } else {
    // s t 都为空返回 true. 为了判断最底层节点都没有的情况
    return !s && !t;
  }
}

console.log('递归判断对称二叉树 > ', isSymmetricTreeRecursive(symmetricTree));
console.log('递归判断非对称二叉树 > ', isSymmetricTreeRecursive(notSymmetricTree));


console.log('迭代判断对称二叉树 > ', isSymmetricTreeIterative(symmetricTree));
console.log('迭代判断非对称二叉树 > ', isSymmetricTreeIterative(notSymmetricTree));