创办网站需要多少钱,ux与ui设计的区别,汕头网络推广哪里好,上海景泰建设股份有限公司网站Problem: 988. 从叶结点开始的最小字符串 文章目录 题目描述思路复杂度Code 题目描述 思路
遍历思想(利用二叉树的先序遍历) 在先序遍历的过程中#xff0c;用一个变量path拼接记录下其组成的字符串#xff0c;当遇到根节点时再将其反转并比较大小#xff08;字典顺序大小用一个变量path拼接记录下其组成的字符串当遇到根节点时再将其反转并比较大小字典顺序大小同时更新较小的结果字符串其中要注意的操作是字符串的反转与更新 复杂度
时间复杂度: O ( n ) O(n) O(n);其中 n n n为二叉树的节点个数 空间复杂度: O ( h ) O(h) O(h)其中 h h h为二叉树的高度 Code
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public String smallestFromLeaf(TreeNode root) {traverse(root);return res;}StringBuilder path new StringBuilder();String res null;private void traverse(TreeNode root) {if (root null) {return;}if (root.left null root.right null) {// Find the leaf node and compare the path// with the smallest lexicographic orderpath.append((char)(a root.val));// The resulting string is from leaf to root,// so inversion is requiredpath.reverse();String s path.toString();if (res null || res.compareTo(s) 0) {res s;}// Recover and properly maintain elements in pathpath.reverse();path.deleteCharAt(path.length() - 1);return;}path.append((char)(a root.val));traverse(root.left);traverse(root.right);path.deleteCharAt(path.length() - 1);}
}
