[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]
ツリーの前の順序に関しては、ツリーの様々な遍歴が参照可能なデータ構造に慣れていない場合は、前の順序で巡回し、中の順に巡回し、後の順序で巡回します.
確かに木の遍歴は一般的に再帰方式を採用しています.第一回目のコードは怠けてスタックの方法で実現しました.
再帰的な形に戻る.
テーマリンク:https://leetcode.com/problems/binary-tree-preorder-traversal/
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/