2020-07-07-PHP 实现修剪二叉树

layout: posttitle: PHP 实现修剪二叉树
subtitle: PHP 实现修剪二叉树
date: 2020-07-07
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode
- 修剪二叉树

修剪二叉树

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

示例 1:

输入: 
    1
   / \
  0   2
  L = 1
  R = 2
输出: 
    1
      \
       2

示例 2:

输入: 
    3
   / \
  0   4
   \
    2
   /
  1
  L = 1
  R = 3
输出: 
      3
     / 
   2   
  /
 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trim-a-binary-search-tree

解题思路

递归遍历二叉树，进行特殊情况的判断，如果 < $L，则只遍历他的右子树，如果 > $R，则只遍历左子树，其他在区间内的相当于重新赋值，无需额外处理。

php 代码

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @param Integer $L
     * @param Integer $R
     * @return TreeNode
     */
    function trimBST($root, $L, $R) {
        if ($root == null) {
            return $root;
        }
        if ($root->val < $L) {
            return $this->trimBST($root->right, $L, $R);
        }
        if ($root->val > $R) {
            return $this->trimBST($root->left, $L, $R);
        }
        $root->left = $this->trimBST($root->left, $L, $R);
        $root->right = $this->trimBST($root->right, $L, $R);
        return $root;
    }
}

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券