Javaデータ構造四の——二叉木の前、中、後順遍歴
40813 ワード
プログラムはプログラムCreekから
前の順序:
Preorder binary tree traversal is a classic interview problem about trees. The key to solve this problem is to understand the following: What is preorder? (parent node is processed before its children) Use Stack from Java Core library
It is not obvious what preorder for some strange cases. However, if you draw a stack and manually execute the program, how each element is pushed and popped is obvious.
The key to solve this problem is using a stack to store left and right children, and push right child first so that it is processed after the left child.
以上のプログラムの考え方は深さ優先探索(DFS)に似ているが,ここではまず現在のノードを遍歴し,左を優先して遍歴しただけである.
私は先に見た後序遍歴なので、自分が実現した前序遍歴は後序遍歴のように書かれています.手順は次のとおりです.
九章アルゴリズムの様々なバージョンの答え
中間パス:
The key to solve inorder traversal of binary tree includes the following: The order of "inorder"is: left child -> parent -> right child Use a stack to track nodes Understand when to push node into the stack and when to pop node out of the stack
依然として後続の遍歴の全体的な考え方を根ざして遍歴すれば、区分はいつ下へ行くのか、いつ遍歴するのか、左上、右上の状況は、非常に遍歴しやすい.このような思想はやはり比較的に良くて、比較的に通用します.手順は次のとおりです.
後の順序:
再帰アルゴリズム:
再帰アルゴリズムは簡単です.プログラムは九章アルゴリズムから来ています.
反復解法:
2つのポインタprevとcurrを使用して、現在および最後にアクセスしたノードをそれぞれ指します.
全体の原則は以下の通りである.
1.まず左の木を通って、遍歴して、
2.親ノード(この場合は左上)を通って右ノードを取得し、
3.右の木を通って、遍歴して、
4.再び親ノード(この場合は右上)を通り、
5.親ノードを巡回します.
まず、次の事実を明らかにします.
①左へまっすぐに延びると、currは常にprevの前方(下)にあり、すなわち、curr=prevという条件を満たす.left.②右に行くと、満足:curr==prev.right.
③左端から上がったときに満足:prev==curr.left;④それに応じて右端から上がったときに満足する:prev==curr.right.
パス手順:
まず,我々は下に進み,経路に沿って左葉または左サブノードのないノードまで左に延び,①に対応する.サブツリーが遍歴した後、上へ行きます.左ノードが遍歴した後、または左サブツリーが遍歴した後、左から上へ行きます.この場合、③に対応します.このとき「初めて親ノードを通過する」は、右の子ツリーが空でない場合は右の子ツリーを取得し(右の子ノードをスタックに押し込む)、次に下に進み、②に対応して右の子ツリーを通過する(右の子ツリーを遍歴する場合は、左の子ツリーから先に手を出し、この場合は上記①の手順をループする).右サブツリーの遍歴が完了すると、右から上へ、④に対応します.この場合は、親ノードを2回目に通過します.上へ歩き続け、左から上へ③か、右から上へ④かを判断し続ける.
以上の考えがあれば、プログラムは書きやすいです.判断条件を知るだけで、いつ下に行く必要があるのか、ノードを巡る必要があるのか、whileループを書くことができます.
判断条件:
これも明らかになった,A)当初prev=nullの時;左ノードを巡回し、初めて親ノードを通過するとcurr==prev.left;左サブツリーを巡回する、初めて親ノードを通過し、親ノードの右サブツリーが空でない場合、curr==prev.right、下へ行く必要があります.
AA)curr==prev.right、かつ左右のサブノードがない場合;B)右から上へ,右サブツリーの遍歴が完了し,2回目に親ノードを通過するとprev=currとなる.right;C)左から上へ、初めて親ノードを通過するが、親ノードに右サブツリーがない場合、prev==curr.left、ノードを巡る必要があります.
プログラムを見てプログラムcreekから
The key to to iterative postorder traversal is the following: The order of "Postorder"is: left child -> right child -> parent node. Find the relation between the previously visited node and the current node Use a stack to track nodes
As we go down the tree, check the previously visited node. If it is the parent of the current node, we should add current node to stack. When there is no children for current node, pop it from stack. Then the previous node become to be under the current node for next loop.
まだ実践と整理を待たなければならない.
前の順序:
Preorder binary tree traversal is a classic interview problem about trees. The key to solve this problem is to understand the following:
It is not obvious what preorder for some strange cases. However, if you draw a stack and manually execute the program, how each element is pushed and popped is obvious.
The key to solve this problem is using a stack to store left and right children, and push right child first so that it is processed after the left child.
1 public class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6 }
7
8 public class Solution {
9 public ArrayList<Integer> preorderTraversal(TreeNode root) {
10 ArrayList<Integer> returnList = new ArrayList<Integer>();
11
12 if(root == null)
13 return returnList;
14
15 Stack<TreeNode> stack = new Stack<TreeNode>();
16 stack.push(root);
17
18 while(!stack.empty()){
19 TreeNode n = stack.pop();
20 returnList.add(n.val);
21
22 if(n.right != null){
23 stack.push(n.right);
24 }
25 if(n.left != null){
26 stack.push(n.left);
27 }
28
29 }
30 return returnList;
31 }
32 }以上のプログラムの考え方は深さ優先探索(DFS)に似ているが,ここではまず現在のノードを遍歴し,左を優先して遍歴しただけである.
私は先に見た後序遍歴なので、自分が実現した前序遍歴は後序遍歴のように書かれています.手順は次のとおりです.
1 public class Solution {
2 public List<Integer> preorderTraversal(TreeNode root) {
3 ArrayList<Integer> result = new ArrayList<Integer>();
4
5 if(root == null)
6 return result;
7
8 Stack<TreeNode> stack = new Stack<TreeNode>();
9 stack.push(root);
10
11 TreeNode prev = null;
12 while(!stack.empty()){
13 TreeNode curr = stack.peek();
14
15 if(prev==null||curr==prev.left||curr==prev.right){
16
17 result.add(curr.val);
18
19 if(curr.left!= null){
20 stack.push(curr.left);
21 }else if(curr.right!=null){
22 stack.push(curr.right);
23 }
24 else{
25 stack.pop();
26 }
27 }else if(prev==curr.left){
28 if(curr.right!=null){
29 stack.push(curr.right);
30 }
31 else{
32 stack.pop();
33 }
34 }else if(prev==curr.right){
35 stack.pop();
36 }
37
38 prev = curr;
39 }
40 return result;
41 }
42 }九章アルゴリズムの様々なバージョンの答え
1 Version 0: Non-Recursion (Recommend)
2 /**
3 * Definition for binary tree
4 * public class TreeNode {
5 * int val;
6 * TreeNode left;
7 * TreeNode right;
8 * TreeNode(int x) { val = x; }
9 * }
10 */
11 public class Solution {
12 public List<Integer> preorderTraversal(TreeNode root) {
13 Stack<TreeNode> stack = new Stack<TreeNode>();
14 List<Integer> preorder = new ArrayList<Integer>();
15
16 if (root == null) {
17 return preorder;
18 }
19
20 stack.push(root);
21 while (!stack.empty()) {
22 TreeNode node = stack.pop();
23 preorder.add(node.val);
24 if (node.right != null) {
25 stack.push(node.right);
26 }
27 if (node.left != null) {
28 stack.push(node.left);
29 }
30 }
31
32 return preorder;
33 }
34 }
35
36 //Version 1: Traverse
37 public class Solution {
38 public ArrayList<Integer> preorderTraversal(TreeNode root) {
39 ArrayList<Integer> result = new ArrayList<Integer>();
40 traverse(root, result);
41 return result;
42 }
43
44 private void traverse(TreeNode root, ArrayList<Integer> result) {
45 if (root == null) {
46 return;
47 }
48
49 result.add(root.val);
50 traverse(root.left, result);
51 traverse(root.right, result);
52 }
53 }
54
55 //Version 2: Divide & Conquer
56 public class Solution {
57 public ArrayList<Integer> preorderTraversal(TreeNode root) {
58 ArrayList<Integer> result = new ArrayList<Integer>();
59 // null or leaf
60 if (root == null) {
61 return result;
62 }
63
64 // Divide
65 ArrayList<Integer> left = preorderTraversal(root.left);
66 ArrayList<Integer> right = preorderTraversal(root.right);
67
68 // Conquer
69 result.add(root.val);
70 result.addAll(left);
71 result.addAll(right);
72 return result;
73 }
74 }中間パス:
The key to solve inorder traversal of binary tree includes the following:
1 //Definition for binary tree
2 public class TreeNode {
3 int val;
4 TreeNode left;
5 TreeNode right;
6 TreeNode(int x) { val = x; }
7 }
8
9 public class Solution {
10 public ArrayList<Integer> inorderTraversal(TreeNode root) {
11 // IMPORTANT: Please reset any member data you declared, as
12 // the same Solution instance will be reused for each test case.
13 ArrayList<Integer> lst = new ArrayList<Integer>();
14
15 if(root == null)
16 return lst;
17
18 Stack<TreeNode> stack = new Stack<TreeNode>();
19 //define a pointer to track nodes
20 TreeNode p = root;
21
22 while(!stack.empty() || p != null){
23
24 // if it is not null, push to stack
25 //and go down the tree to left
26 if(p != null){
27 stack.push(p);
28 p = p.left;
29
30 // if no left child
31 // pop stack, process the node
32 // then let p point to the right
33 }else{
34 TreeNode t = stack.pop();
35 lst.add(t.val);
36 p = t.right;
37 }
38 }
39
40 return lst;
41 }
42 }依然として後続の遍歴の全体的な考え方を根ざして遍歴すれば、区分はいつ下へ行くのか、いつ遍歴するのか、左上、右上の状況は、非常に遍歴しやすい.このような思想はやはり比較的に良くて、比較的に通用します.手順は次のとおりです.
1 public class Solution {
2 public List<Integer> inorderTraversal(TreeNode root) {
3 ArrayList<Integer> result = new ArrayList<Integer>();
4
5 if(root == null)
6 return result;
7
8 Stack<TreeNode> stack = new Stack<TreeNode>();
9 stack.push(root);
10
11 TreeNode prev = null;
12 while(!stack.empty()){
13 TreeNode curr = stack.peek();
14 if(prev==null||curr==prev.left||curr==prev.right){
15 if(curr.left!=null){
16 stack.push(curr.left);
17 }else if(curr.right!=null){
18 result.add(curr.val);
19 stack.push(curr.right);
20 }else{
21 result.add(curr.val);
22 stack.pop();
23 }
24 }else if(prev==curr.left){
25 result.add(curr.val);
26 if(curr.right!=null){
27 stack.push(curr.right);
28 }else{
29 stack.pop();
30 }
31
32 }else if(prev==curr.right){
33 stack.pop();
34 }
35 prev=curr;
36 }//while
37 return result;
38 }
39 }後の順序:
再帰アルゴリズム:
再帰アルゴリズムは簡単です.プログラムは九章アルゴリズムから来ています.
1 //Recursive
2 public ArrayList<Integer> postorderTraversal(TreeNode root) {
3 ArrayList<Integer> result = new ArrayList<Integer>();
4
5 if (root == null) {
6 return result;
7 }
8
9
10 result.addAll(postorderTraversal(root.left));
11 result.addAll(postorderTraversal(root.right));
12 result.add(root.val);
13
14 return result;
15 }反復解法:
2つのポインタprevとcurrを使用して、現在および最後にアクセスしたノードをそれぞれ指します.
全体の原則は以下の通りである.
1.まず左の木を通って、遍歴して、
2.親ノード(この場合は左上)を通って右ノードを取得し、
3.右の木を通って、遍歴して、
4.再び親ノード(この場合は右上)を通り、
5.親ノードを巡回します.
まず、次の事実を明らかにします.
①左へまっすぐに延びると、currは常にprevの前方(下)にあり、すなわち、curr=prevという条件を満たす.left.②右に行くと、満足:curr==prev.right.
③左端から上がったときに満足:prev==curr.left;④それに応じて右端から上がったときに満足する:prev==curr.right.
パス手順:
まず,我々は下に進み,経路に沿って左葉または左サブノードのないノードまで左に延び,①に対応する.サブツリーが遍歴した後、上へ行きます.左ノードが遍歴した後、または左サブツリーが遍歴した後、左から上へ行きます.この場合、③に対応します.このとき「初めて親ノードを通過する」は、右の子ツリーが空でない場合は右の子ツリーを取得し(右の子ノードをスタックに押し込む)、次に下に進み、②に対応して右の子ツリーを通過する(右の子ツリーを遍歴する場合は、左の子ツリーから先に手を出し、この場合は上記①の手順をループする).右サブツリーの遍歴が完了すると、右から上へ、④に対応します.この場合は、親ノードを2回目に通過します.上へ歩き続け、左から上へ③か、右から上へ④かを判断し続ける.
以上の考えがあれば、プログラムは書きやすいです.判断条件を知るだけで、いつ下に行く必要があるのか、ノードを巡る必要があるのか、whileループを書くことができます.
判断条件:
これも明らかになった,A)当初prev=nullの時;左ノードを巡回し、初めて親ノードを通過するとcurr==prev.left;左サブツリーを巡回する、初めて親ノードを通過し、親ノードの右サブツリーが空でない場合、curr==prev.right、下へ行く必要があります.
AA)curr==prev.right、かつ左右のサブノードがない場合;B)右から上へ,右サブツリーの遍歴が完了し,2回目に親ノードを通過するとprev=currとなる.right;C)左から上へ、初めて親ノードを通過するが、親ノードに右サブツリーがない場合、prev==curr.left、ノードを巡る必要があります.
プログラムを見てプログラムcreekから
The key to to iterative postorder traversal is the following:
As we go down the tree, check the previously visited node. If it is the parent of the current node, we should add current node to stack. When there is no children for current node, pop it from stack. Then the previous node become to be under the current node for next loop.
1 //Definition for binary tree 2 public class TreeNode { 3 int val; 4 TreeNode left; 5 TreeNode right; 6 TreeNode(int x) { val = x; } 7 } 8 9 10 public class Solution { 11 public ArrayList<Integer> postorderTraversal(TreeNode root) { 12 13 ArrayList<Integer> lst = new ArrayList<Integer>(); 14 15 if(root == null) 16 return lst; 17 18 Stack<TreeNode> stack = new Stack<TreeNode>(); 19 stack.push(root); 20 21 TreeNode prev = null; 22 while(!stack.empty()){ 23 TreeNode curr = stack.peek(); 24 25 // go down the tree. 26 //check if current node is leaf, if so, process it and pop stack, 27 //otherwise, keep going down 28 if(prev == null || prev.left == curr || prev.right == curr){ 29 //prev == null is the situation for the root node 30 if(curr.left != null){ 31 stack.push(curr.left); 32 }else if(curr.right != null){ 33 stack.push(curr.right); 34 }else{ 35 stack.pop(); 36 lst.add(curr.val); 37 } 38 39 //go up the tree from left node 40 //need to check if there is a right child 41 //if yes, push it to stack 42 //otherwise, process parent and pop stack 43 }else if(curr.left == prev){ 44 if(curr.right != null){ 45 stack.push(curr.right); 46 }else{ 47 stack.pop(); 48 lst.add(curr.val); 49 } 50 51 //go up the tree from right node 52 //after coming back from right node, process parent node and pop stack. 53 }else if(curr.right == prev){ 54 stack.pop(); 55 lst.add(curr.val); 56 } 57 58 prev = curr; 59 } 60 61 return lst; 62 } 63 }まだ実践と整理を待たなければならない.