D130 257. Binary Tree Paths
题目链接
题目分析
给定一个二叉树，返回所有子节点的路径。
解题思路
这道题好像也没什么难度，在先序遍历的同时，把父节点的集合都塞进一个数组中。当当前节点是叶子节点时，把所有节点都拼接成字符串，塞入类属性中。遍历完右节点时，说明遍历完当前节点了，故把自己弹出父节点列表。
最终代码
<?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
* @return String[]
*/
private $paths = [];
function binaryTreePaths($root) {
$parents = [];
$this->preOrder($root, $parents);
return $this->paths;
}
function preOrder($node, &$parents){
if(is_null($node->val)){
return;
}
$parents[] = $node->val;
if(is_null($node->left) && is_null($node->right)){
$this->paths[] = implode('->', $parents);
array_pop($parents);
return;
}
$this->preOrder($node->left, $parents);
$this->preOrder($node->right, $parents);
array_pop($parents);
return;
}
}
若觉得本文章对你有用，欢迎用爱发电资助。
