두 갈래 나무의 흔한 반복 방식과 제목 총결

18756 단어

두 갈래 나무의 흔한 반복 방식과 제목 총결


두 갈래 나무는 흔히 훑어보는 방식을 볼 수 있다


트리 정의/** \* Definition for a binary tree node. \* public class TreeNode { \* int val; \* TreeNode left; \* TreeNode right; \* TreeNode(int x) { val = x; } \* } */

(1) 앞의 순서를 두루 훑어보다


루트 노드에 접근한 다음 왼쪽 트리를 앞뒤로 훑어보고 오른쪽 트리를 앞뒤로 훑어보십시오.
(a) 귀속 방법 두루

void preoder(TreeNode T)

{

        if(T==null) return ;

        sysytem.out。print(T.val);

        preoder(TreeNode T.left);

        preoder(TreeNode T.right);

}



(b) 


class Solution {
  public List<Integer> preorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    if (root == null) {
      return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pollLast();
      output.add(node.val);
      if (node.right != null) {
        stack.add(node.right);
      }
      if (node.left != null) {
        stack.add(node.left);
      }
    }
    return output;
  }
}


(2) 반복


(a) 귀속
void preoder(TreeNode T)

{

    if(T==null) return ;
    preoder(TreeNode T.left);

    sysytem.out.print(T.val);


    preoder(TreeNode T.right);


}

(b) 비귀속
public void inOrder() {
		Node current = root;
		// LinkedList 
		LinkedList<Node> s = new LinkedList<Node>();
		while (current != null || !s.isEmpty()) {
			while (current != null) {
				s.addFirst(current);
				current = current.left;
			}
			if (!s.isEmpty()) {
				current = s.removeFirst();
				System.out.print(current.data + " -> ");
				current = current.right;
			}
		}
	}


(3) 뒤따르기


(a) 귀속
public static void postOrderRecur(TreeNode head) {
    if (head == null) {
        return;
    }
    postOrderRecur(head.left);
    postOrderRecur(head.right);
    System.out.print(head.value + " ");
}


(b) 비귀속
public static void postOrderIteration(TreeNode head) {
		if (head == null) {
			return;
		}
		Stack<TreeNode> stack1 = new Stack<>();
		Stack<TreeNode> stack2 = new Stack<>();
		stack1.push(head);
		while (!stack1.isEmpty()) {
			TreeNode node = stack1.pop();
			stack2.push(node);
			if (node.left != null) {
				stack1.push(node.left);
			}
			if (node.right != null) {
				stack1.push(node.right);
			}
		}
		while (!stack2.isEmpty()) {
			System.out.print(stack2.pop().value + " ");
		}
	}

	if (node.right != null) {
				stack1.push(node.right);
			}
		}
		while (!stack2.isEmpty()) {
			System.out.print(stack2.pop().value + " ");
		}
	}

좋은 웹페이지 즐겨찾기