✏️9. 反转二叉树 (leetcode226）
/** * @param TreeNode $root * @return TreeNode */ function invertTree($root) { if(!$root) return null; $list=[]; array_push($list,$root); while(!empty($list)){ $node=array_shift($list); $temp=$node->left; $node->left=$node->right; $node->right=$temp; if($node->left) array_push($list,$node->left); if($node->right) array_push($list,$node->right); } return $root; }
递归解
/** * @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; }
✏️10. 给定单链表 (值有序) 转化成平衡二叉查找树 (leetcode109）
先将链表数据转换成有序数组，然后利用二分查找的特性，构建左右子树。
/** * Definition for a singly-linked list. * class ListNode { * public $val = 0; * public $next = null; * function __construct($val) { $this->val = $val; } * } */ /** * 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 ListNode $head * @return TreeNode */ function sortedListToBST($head) { $data=[]; while($head){ array_push($data,$head->val); $head=$head->next; } return $this->helper($data); } function helper($data) { if(!$data) return ; $middle=floor(count($data)/2); $node=new TreeNode($data[$middle]); $node->left=$this->helper(array_slice($data,0,$middle)); $node->right=$this->helper(array_slice($data,$middle+1)); return $node; } }
✏️11. 强盗打劫版本 3 (leetcode337）
最后的目的算出最多能抢金额数而不触发报警器。除了根节点，每一个结点只有一个父节点，能直接相连的两个节点不能同时抢，比如图 1，抢了根节点，直接相连的左右子结点就不能抢。所以要么抢根节点的左右子结点，要么根结点 + 根结点 ->left->right + 根结点 ->right->right。
//递归 /** * @param TreeNode $root * @return Integer */ function rob($root) { if($root==null){ return 0; } $res1=$root->val; if($root->left !=null) { $res1 +=$this->rob($root->left->left)+$this->rob($root->left->right); } if($root->right !=null){ $res1 +=$this->rob($root->right->left)+$this->rob($root->right->right); } $res2=$this->rob($root->left)+$this->rob($root->right); return max($res1,$res2); }
上面那种大量的重复计算，改进一下。
如果结点不存在直接返回 0，对左右结点分别递归，设置了 4 个变量，ll 和 lr 分别表示左子结点的左右子结点的最大金额数，rl 和 rr 分别表示右子结点的左右子结点的最大金额数。所以我们最后比较的还是两种情况，第一种就是当前结点 + 左右子结点的左右子结点的值 (即这里定义的 ll,lr,rl,rr). 第二种是当前结点的左右子结点的值 (也就是说我只抢当前结点的子结点，不抢当前结点和孙子结点)，再通俗的说就是如果树的层数是 3 层，要么抢中间一层，要么抢上下两层，谁钱多抢谁。
/** * @param TreeNode $root * @return Integer */ function rob($root) { $l=0;$r=0; return $this->countMax($root,$l,$r); } function countMax($root,&$l,&$r){ if($root==null) return 0; $ll=0;$lr=0;$rl=0;$rr=0; $l=$this->countMax($root->left,$ll,$lr); $r=$this->countMax($root->right,$rl,$rr); return max($root->val+$ll+$lr+$rl+$rr,$l+$r); }
✏️12. 判断二叉树路径和是否存在 (leetcode112）
只要使用深度优先算法思想遍历每一条完整的路径，如果是个空树直接 false，如果结点没有左右子树 (说明此时已然是叶子结点，判断值是否是给定值，这个条件正好是递归终止的条件)，相等直接返回 true，根据这个推导出递归公式。
/** * @param TreeNode $root * @param Integer $sum * @return Boolean */ function hasPathSum($root, $sum) { if($root==null){ return false; } if($root->left ==null && $root->right==null && $root->val==$sum) return true; return $this->hasPathSum($root->left,$sum-$root->val) || $this->hasPathSum($root->right,$sum-$root->val); }
改成迭代
/** * @param TreeNode $root * @param Integer $sum * @return Boolean */ function hasPathSum($root, $sum) { if($root==null){ return false; } $res=[]; array_push($res,$root); while(!empty($res)){ $node=array_shift($res); if(!$node->left && !$node->right ){ if($node->val==$sum) return true; } if($node->left){ $node->left->val +=$node->val; array_push($res,$node->left); } if($node->right){ $node->right->val +=$node->val; array_push($res,$node->right); } } return false; }
✏️13. 判断是否是二叉查找树 (leetcode98）
思路有两种，二叉查找树的特点就是左子树上的结点都小于根结点，右子树上的结点都大于根节点。所以有两个方向，可以分别递归的判断左子树，右子树。或者拿左子树上的最大值，右子树上的最小值分别对应根结点进行判断。
/** * 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 * @return Boolean */ function isValidBST($root) { return $this->helper($root,null,null); } function helper($root,$lower,$upper){ if($root==null) return true; $res=$root->val; if($lower !==null && $res<=$lower) return false; if($upper !==null && $res>=$upper) return false; if(!$this->helper($root->left,$lower,$res)) return false; if(!$this->helper($root->right,$res,$upper)) return false; return true; } }
✏️14. 找出二叉树最后一层最左边的值 (leetcode513）
思路有两种，二叉查找树的特点就是左子树上的结点都小于根结点，右子树上的结点都大于根节点。所以有两个方向，可以分别递归的判断左子树，右子树。或者拿左子树上的最大值，右子树上的最小值分别对应根结点进行判断。
/** * @param TreeNode $root * @return Integer */ function findBottomLeftValue($root) { $data=[]; array_push($data,$root); while(!empty($data)){ $node = array_shift($data); if($node->right) array_push($data,$node->right); if($node->left) array_push($data,$node->left); } return $node->val; }
