[leetcode]Binary Tree Prorder Traversal

4312 ワード

テーマの説明は以下の通りです.
Gven a binary tree,return the preorder trversal of its nodes’values.
For example:
Given binary tree{1、啱、2、3}
1\2/3
return[1,2,3]
ツリーの前の順序に関しては、ツリーの様々な遍歴が参照可能なデータ構造に慣れていない場合は、前の順序で巡回し、中の順に巡回し、後の順序で巡回します.
確かに木の遍歴は一般的に再帰方式を採用しています.第一回目のコードは怠けてスタックの方法で実現しました.
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> resList = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return resList;
        TreeNode tmp;
        stack.add(root);
        while(!stack.isEmpty()){
            tmp = stack.pop();
            resList.add(tmp.val);
            if(tmp.left != null || tmp.right != null){
                if(tmp.right != null) stack.push(tmp.right);
                if(tmp.left != null) stack.push(tmp.left);
            }
        }
        return resList;
    }
}
結果、runtimeは2.77%の提出を下しました.
再帰的な形に戻る.
public class Solution {
    List<Integer> resList = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return resList;
        getResultList(root);
        return resList;
    }

    private void getResultList(TreeNode root) {
        resList.add(root.val);
        if(root.left != null || root.right != null){
            if(root.left != null) getResultList(root.left);
            if(root.right != null) getResultList(root.right);
        }
    }
}
コードは簡潔になりましたが、性能が向上しました.スタックの読み取りはまだ遅くなりましたので、これからは大人しく再帰します.
テーマリンク:https://leetcode.com/problems/binary-tree-preorder-traversal/