算法-二叉树

遍历二叉树

深度优先遍历 DFS

二叉树的深度优先遍历可以细分为：先序遍历、中序遍历、后续遍历。

• 前序遍历：根节点 -> 左子树 -> 右子树
• 中序遍历：左子树 -> 根节点 -> 右子树
• 后续遍历：左子树 -> 右子树 -> 根节点

  <?php
      class BTreeNode {
          public $data;  //数据域
          public $LeftHand = NULL;  //左指针
          public $RightHand = NULL ; //右指针
          
          public function __construct($data) {
              if(!empty($data)) {
                  $this->data = $data;
              }
          }
          
          //先序遍历（根，左，右）递归实现
          public  function PreTraverseBTree($BTree){
               if (NULL !== $BTree){
                  var_dump($BTree->data);//根
                  if (NULL !== $BTree->LeftHand){
                      $this->PreTraverseBTree($BTree->LeftHand); //递归遍历左树
                  }
                  if (NULL !== $BTree->RightHand){
                      $this->PreTraverseBTree($BTree->RightHand); //递归遍历右树
                  }
              }
          }
          
          //中序遍历(左，根，右)递归实现
          public  function  InTraverseBTree($BTree){
              if (NULL !== $BTree){
                  if (NULL !== $BTree->LeftHand){
                      $this->InTraverseBTree($BTree->LeftHand); //递归遍历左树
                  }
                  var_dump($BTree->data); //根
                  if (NULL !== $BTree->RightHand){
                      $this->InTraverseBTree($BTree->RightHand); //递归遍历右树
                  }
              }
          }
          
          //后序遍历(左，右，根)递归实现
          public  function  FexTarverseBTree($BTree){
              if (NULL !== $BTree){
                  if (NULL !== $BTree->LeftHand){
                      $this->FexTarverseBTree($BTree->LeftHand); //递归遍历左树
                  }
                  if (NULL !== $BTree->RightHand){
                      $this->FexTarverseBTree($BTree->RightHand); //递归遍历右树
                  }
                  var_dump($BTree->data); //根
              }
          }
      }
      
     header("Content-Type:text/html;charset=utf-8");
     echo '先的内存为'.var_dump(memory_get_usage());
     echo '<hr/>'; 
     //创建五个节点
     $A  = new  BTreeNode('A');
     $B  = new  BTreeNode('B');
     $C  = new  BTreeNode('C');
     $D  = new  BTreeNode('D');
     $E  = new  BTreeNode('E');
     //连接形成一个二叉树
     $A->LeftHand  = $B;
     $A->RightHand = $C;
     $C->LeftHand  = $D;
     $D->RightHand = $E;  
     //先序遍历
     echo '先序遍历的结果'.'<br>';
     $A->PreTraverseBTree($A);
     echo '<br/>中序遍历的结果'.'<br>';
     $A->InTraverseBTree($A); 
     echo  '<br/>后序列遍历的结果'.'<br/>';
     $A->FexTarverseBTree($A); 
     echo '<hr/>';
     echo '后的内存为'.var_dump(memory_get_usage());

广度优先遍历 BFS

广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。

// Definition for a binary tree node
class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;

    public function __construct($value)
    {
        $this->val = $value;
    }
}

版本1：数组模拟队列，先入先出

class Solution {
    /**
     * @param TreeNode $root
     * @return array
     */
    public function levelOrder(TreeNode $root)
    {
        $res = $arr = [];
        if ($root == null) {
            return $res;
        }
        array_push($arr, $root);
        $level = 0;
        while ($count = count($arr)) {
            for ($i = $count; $i > 0; $i--) {
                $node = array_shift($arr); // 先入先出
                $res[$level][] = $node->val;
                if ($node->left != null) array_push($arr, $node->left);
                if ($node->right != null) array_push($arr, $node->right);
            }
            $level++;
        }
        return $res;
    }
}

版本2：使用PHP SplQueue

SplQueue 类通过使用一个双向链表来提供队列的主要功能。

class Solution {
    /**
     * @param TreeNode $root
     * @return array
     */
    public function levelOrder(TreeNode $root)
    {
        $res = [];
        $arr = new SplQueue();
        if ($root == null) {
            return $res;
        }
        $arr->enqueue($root);
        $level = 0;
        while ($count = count($arr)) {
            for ($i = $count; $i > 0; $i--) {
                $node = $arr->dequeue(); // 删除第一位
                $res[$level][] = $node->val;
                if ($node->left != null) $arr->enqueue($node->left);
                if ($node->right != null) $arr->enqueue($node->right);
            }
            $level++;
        }
        return $res;
    }
}

版本3：递归

class Solution {
    /**
     * @param TreeNode $root
     * @return array
     */
    public function levelOrder(TreeNode $root)
    {
        $res = [];
        $this->level($root, 0, $res);
        return $res;
    }
    
    public function level($root, $level, &$res)
    {
        if ($root == null) {
            return null;
        }
        $res[$level][] = $root->val;
        $level++;
        if ($root->left != null) {
            $this->level($root->left, $level, $res);
        }
        if ($root->right != null) {
            $this->level($root->right, $level, $res);
        }
    }
}

判断是否是二叉搜索树

判断一颗树是否是二叉搜索树，一棵树是BST需要满足

• 一个节点的值大于它左子树所有节点的值
• 一个节点的值小于它右子树所有节点的值
• 左右子树也必须是二叉搜索树

所以只需要遍历每个节点，判断

• 该节点值是否大于左子树的最大值
• 该节点值是否小于右子树的最小值

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val;
 *     public $left;
 *     public $right;
 * };
 */
class Solution {
    public function isValidBST(TreeNode $root) {
        if(!$root)   return true;
        //大于左子树的最大值
        $leftNode = $root->left;
        while($leftNode)
        {
            if($root->val <= $leftNode->val){
                return false;
            }
            $leftNode = $leftNode->right;
        }
        //小于右子树的最小值
        $rightNode = $root->right;
        while($rightNode)
        {
            if($root->val >= $rightNode->val){
                return false;
            }
            $rightNode = $rightNode->left;
        }
        if(isValidBST($root->left) && isValidBST($root->right)){
            return true;
        }else {
            return false;
        }
    }
}