leetcode--Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
For example: Given binary tree
return
分類:ツリー
題意:前順に二叉木を遍歴する
解法1:再帰
解法2:スタックシミュレーションを使用して再帰する
解法3:morris二叉木遍歴,空間O(1),時間O(n)
ループプロシージャは、ノードrootに対して左サブツリーがあるかどうかを判断し、ない場合はそのノードにアクセスし、現在のノードを右ノードに設定し、上記のプロシージャを繰り返します.
左サブツリーがあり、左サブツリーの右端にあるノード(つまり、前のシーケンスで左サブツリーが最後にアクセスしたノード)を巡回します.
このノードのrightが空の場合、このノードのrightを現在のノードrootに設定し、rootにアクセスし、現在のノードをrootの左ノードに設定します.
ノードrightがすでに指向している場合は、このノードがスレッド化されていることを示し、現在のノードをrootの右ノードに設定し、rightをnullに設定してスレッドをクリアします.
For example: Given binary tree
{1,#,2,3}
, 1
\
2
/
3
return
[1,2,3]
. 分類:ツリー
題意:前順に二叉木を遍歴する
解法1:再帰
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root!=null) helper(res,root);
return res;
}
public void helper(List<Integer> res,TreeNode n){
res.add(n.val);
if(n.left!=null) helper(res, n.left);
if(n.right!=null) helper(res, n.right);
}
}
解法2:スタックシミュレーションを使用して再帰する
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root==null) return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.add(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
res.add(cur.val);
if(cur.right!=null) stack.add(cur.right);// ,
if(cur.left!=null) stack.add(cur.left);// ,
}
return res;
}
}
解法3:morris二叉木遍歴,空間O(1),時間O(n)
ループプロシージャは、ノードrootに対して左サブツリーがあるかどうかを判断し、ない場合はそのノードにアクセスし、現在のノードを右ノードに設定し、上記のプロシージャを繰り返します.
左サブツリーがあり、左サブツリーの右端にあるノード(つまり、前のシーケンスで左サブツリーが最後にアクセスしたノード)を巡回します.
このノードのrightが空の場合、このノードのrightを現在のノードrootに設定し、rootにアクセスし、現在のノードをrootの左ノードに設定します.
ノードrightがすでに指向している場合は、このノードがスレッド化されていることを示し、現在のノードをrootの右ノードに設定し、rightをnullに設定してスレッドをクリアします.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root==null) return res;
TreeNode cur = root;
TreeNode pre = null;
while(cur!=null){// ,
if(cur.left==null){//
res.add(cur.val);//
cur = cur.right;//
}else{//
pre = cur.left;
while(pre.right!=null&&pre.right!=cur){//
pre = pre.right;
}
if(pre.right==null){//
pre.right = cur;//
res.add(cur.val);//
cur = cur.left;//
}else{// , ,
pre.right = null;//
cur = cur.right;//
}
}
}
return res;
}
}