✏️Leetcode 经典二叉树题目集合
开题：这位同志，麻烦你手写一个红黑树出来...... 告辞！！！！！
✏️1. 二叉树的前序遍历（leetcode144）
前序遍历，先访问根结点，然后在访问左子树，最后访问右子树。可以利用栈的特点，这里我结合了队列和栈的特点来实现。先压入树，取出根节点。先把根节点值 push 到队列中，然后把右子树压入栈中，最后压入左子树。返回队列。当然你可以调整成你想要的实现方式。(只要前中后序顺序理解正确即可)
/** * 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](https://learnku.com/users/31554) Integer[] */ function preorderTraversal($root) { $res=[]; $list=[]; array_unshift($res,$root); while(!empty($res)){ $current=array_shift($res); if($current==null) continue; array_push($list,$current->val); array_unshift($res,$current->right); array_unshift($res,$current->left); } return $list; } }
✏️2. 二叉树的中序遍历 (leetcode94)
/** * @param TreeNode $root * @return Integer[] */ function inorderTraversal($root) { $res=[]; $this->helper($root,$res); return $res; } function helper($root,&$res){ if($root !=null){ if($root->left !=null) $this->helper($root->left,$res); array_push($res,$root->val); if($root->right !=null) $this->helper($root->right,$res); } }
或者不用递归
/** * @param TreeNode $root * @return Integer[] */ function inorderTraversal($root) { $res=[]; $list=[]; while(!empty($list) || $root !=null){ while($root != null){ array_unshift($list,$root); $root=$root->left; } $root=array_shift($list); array_push($res,$root->val); $root=$root->right; } return $res; }
✏️3. 二叉树的后序遍历 (leetcode145)
/** * @param TreeNode $root * @return Integer[] */ function postorderTraversal($root) { $list=[]; $res=[]; array_push($list,$root); while(!empty($list)){ $node=array_shift($list); if(!$node) continue; array_unshift($res,$node->val); array_unshift($list,$node->left); array_unshift($list,$node->right); } return $res; } }
✏️4. 二叉树的层次遍历 (leetcode102)
DFS 和 BFS 都可以解，竟然已经要我们按照层打印了，那么先使用 BFS，思路就是先判断树是否是空，不是空加入一个队列的结构中，如果队列不为空，取出头元素，那么当前元素表示的就是当前这一层了，所以只需要遍历这一层里的所有的元素即可，然后下一层....
class Solution { /** * @param TreeNode $root * @return Integer[][] */ function levelOrder($root) { if(empty($root)) return []; $result = []; $queue = []; array_push($queue,$root); while(!empty($queue)){ $count = count($queue); $leveQueue = []; for($i = 0;$i<$count;$i++){ $node = array_shift($queue); array_push($leveQueue,$node->val); if($node->left) array_push($queue,$node->left); if($node->right) array_push($queue,$node->right); } array_push($result,$leveQueue); } return $result; } }
如果使用 DFS 的话，就是一条路走到黑，然后再重新一路路的退回来再找下一路，所以这样的话，每一次我们需要记录一下当前他所在的这个点属于哪一层即可，代码用递归实现。
class Solution { /** * @param TreeNode $root * @return Integer[][] */ function levelOrder($root) { if(empty($root)) return []; $result=[]; $this->helper($result,$root,0); return $result; } function helper(&$result,$node,$level){ if(empty($node)) return ; if(count($result)<$level+1){ array_push($result,[]); //说明当前行没有结果 } array_push($result[$level],$node->val); $this->helper($result,$node->left,$level+1); $this->helper($result,$node->right,$level+1); } }
✏️5. 二叉树的最大深度 (leetcode104）
DFS 和 BFS 都可以解，竟然已经要我们按照层打印了，那么先使用 BFS，思路就是先判断树是否是空，不是空加入一个队列的结构中，如果队列不为空，取出头元素，那么当前元素表示的就是当前这一层了，所以只需要遍历这一层里的所有的元素即可，然后下一层....
/** * @param TreeNode $root * @return Integer */ function maxDepth($root) { if(empty($root)) return 0; $left = $this->maxDepth($root->left); $right = $this->maxDepth($root->right); return $left<$right? $right+1:$left+1; return max($left,$right)+1; }
✏️6. 二叉树的最小深度 (leetcode111）
DFS 和 BFS 都可以求解
//BFS /** * @param TreeNode $root * @return Integer */ function minDepth($root) { if(empty($root)) return 0; if(!$root->right) return $this->minDepth($root->left)+1; if(!$root->left) return $this->minDepth($root->right)+1; $left=$this->minDepth($root->left); $right=$this->minDepth($root->right); return min($left,$right)+1; } //DFS /** * @param TreeNode $root * @return Integer */ function minDepth($root) { if(empty($root)) return 0; $left=$this->minDepth($root->left); $right=$this->minDepth($root->right); if($left==0 || $right==0) return $left+$right+1; return min($left,$right)+1; }
✏️7. 判断是否是平衡二叉树 (leetcode110）
每一节点的两个子树的深度相差不能超过 1。如果是空树，直接 true。
class Solution { /** * @param TreeNode $root * @return Boolean */ private $result=true; function isBalanced($root) { if(empty($root)) return true; $this->helper($root); return $this->result; } function helper($root) { if(!$root) return ; $left=$this->helper($root->left); $right=$this->helper($root->right); if(abs($left-$right)>1) $this->result=false; return max($left,$right)+1; } }
✏️8. 判断是否是对称二叉树 (leetcode101）
1. 两个子节点都是空，那说明他们是对称的返回 true
2. 一个子节点为空，另一个子节点不为空，false
3. 两个子节点都不为空，但是他们不相等，false
4. 两个子节点不为空且相等，继续判断他们的左子树和右子树，把左子树的左子节点和右子树的右子节点进行比较，把左子树的右子节点和右子树的左子节点进行比较
/** * @param TreeNode $root * @return Boolean */ function isSymmetric($root) { if(empty($root)) return true; return $this->helper($root->left,$root->right); } function helper($l,$r){ if(!$l && !$r) return true; if(!$l || !$r || $l->val != $r->val) return false; return $this->helper($l->left ,$r->right) && $this->helper($l->right,$r->left); }
