Leetcode基础刷题之PHP解析(226. Invert Binary Tree)

2019-4-14 星期日  开始吧

上一题链接 Leetcode基础刷题之PHP解析(198. House Robber Easy)

题目描述

反转二叉树。Leetcode关于树的题很多，我记得刷了很多道了(好吧，没做过特别复杂的)，它的表现形式也是多样化了。今天来看这道简单的吧

题目分析

我们要反转树中所有节点的左右节点，像实现树这样的结构，好吧有时候递归真的是最适合的。

 /**
     * @param TreeNode $root
     * @return TreeNode
     */
    function invertTree($root) {
      if(empty($root)){
          return null;
      }
        $right=$this->invertTree($root->right);
        $left=$this->invertTree($root->left);
        $root->left=$right;
        $root->right=$left;
        return $root;
    }

解法二

我们也可以通过迭代的方式来实现，利用队列的特点实现反转。先把根节点push到队列中，只要判断队列是否为空，每一次从队列中取出一个节点，进行子节点位置的互换，然后再把它的子节点push到队列中，如果是空的就不push

/**
     * @param TreeNode $root
     * @return TreeNode
     */
    function invertTree($root) {
        if(empty($root)){
            return null;
        }
        $queue=[];
        array_push($queue,$root);
        while(!empty($queue)){
            $node=array_shift($queue);
            $temp=$node->left;
            $node->left=$node->right;
            $node->right=$temp;
            if($node->left !=null) array_push($queue,$node->left);
            if($node->right !=null) array_push($queue,$node->right);
        }
        return $root;
    }

 github地址:https://github.com/wuqinqiang/leetcode-php