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

2019-4-14 期日  

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

e1cafee423ee0e54d578ddedf5a91ec9.png

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

吴亲库里 has written 100 articles

情绪只是对自己无能的愤怒

积分:4877 等级:P8 职业:php 城市:杭州

0 条回复

登录后才能进行评论,立即登录?