226.md

✏️Leetcode之PHP版题目解析（225. Implement Stack using Queues）

2019-04-014 吴亲库里 库里的深夜食堂

---

✏️描述

反转二叉树。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;
    }

联系

​