leetcode988. 从叶结点开始的最小字符串

leetcode988. 从叶结点开始的最小字符串

三月 14, 2020

leetcode988. 从叶结点开始的最小字符串

我被dfs整懵了。
我先说我的错误思路：我想用后序遍历找出左子树和右子树较小的那个。但是
   z
   /    
  b    
 /    \
a     a
 /
b
 /
a
这个样例就不行了，因为我最后需要比较ababz和abz的大小，而后序遍历只能比较到abab和ab，这么结果就不对了。

官方解法

dfs，找到所有的可能性，逐一比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  class Solution {
    public String ans="z";
    public String smallestFromLeaf(TreeNode root) {
        traverse(root,new StringBuffer());
        return ans;
    }
    public void traverse(TreeNode root,StringBuffer sbf){
        if(root==null)return ;
        sbf.append((char)(root.val+'a'));
        if(root.left==null&&root.right==null){
        //左右儿子都没有，就说明这个串到头了，得比较
            sbf.reverse();
            String s=new String(sbf);
            if(s.compareTo(ans)<0)ans=s;
            sbf.reverse();
        }
        traverse(root.left,sbf);
        traverse(root.right,sbf);
        sbf.deleteCharAt(sbf.length()-1);
        //每次回溯相当于少了一个字母，所以要把这次遍历加上去的当前节点删掉
    }
}

leetcode 37/100