PHP 实现修剪二叉树

PHP 实现修剪二叉树

author: he xiaodong date: 2020-07-07
修剪二叉树

给定一个二叉搜索树,同时给定最小边界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;
    }
}

顺带推荐买课,用右侧链接有优惠 算法面试通关40讲