Leetcode之PHP版题目解析(101. Symmetric Tree)


2019-3-14 星期四  开始吧

 今天喜提人生第一台Mac,有点小激动,原谅我这么土.

cbe3a049395b50bb9f368381622db3fa.jpg

给定一棵二叉树,判断是否是自身的镜像(围绕他的中心是不是对称)


For example, this binary tree [1,2,2,3,4,4,3] is symmetric

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

图一是对称的,图二不是对称的.

对于根节点的两个子节点,可以分成多种情况

  1. 两个子节点都是空,那说明他们是对称的返回true
  2. 一个子节点为空,另一个子节点不为空,false
  3. 两个子节点都不为空,但是他们不相等,false,
  4. 两个子节点不为空且相等,继续判断他们的子节点(暂且称为左子树和右子树吧),把左子树的左子节点和右子树的右子节点进行比较,把左子树的右子节点和右子树的左子节点进行比较.

所以实现的代码是递归的思想.

  /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isSymmetric($root) {
        if(!$root){
            return true;
        }
        return $this->check_tree($root->left,$root->right);
    }
    
    function check_tree($x,$y){
        if(!$x && !$y){
            return true;
        }
        if(!$x || !$y || $x->val !== $y->val){
            return false;
        }
        return $this->check_tree($x->left,$y->right) &&
            $this->check_tree($x->right,$y->left);
    }

1f470f6cc08b08a61bb25dde8290b7a5.png

leetcode最后运行的时候有时候并不能说明什么,你会发现,有时候一段代码你多次运行耗费的时间是不一样的,所以你不能单从运行结果上来查看代码的效率,还是要通过大0时间复杂度来进行分析,然后调整.


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: 智能提示 mysql客户端:mycli工具介绍

>> 下一篇: Leetcode PHP题解--D6 595. Big Countries