lc 면접 준비: Invert Binary Tree

1441 단어 binary

제목


Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to
     4
   /   \
  7     2
 / \   / \
9   6 3   1

인터페이스:public TreeNode invertTree(TreeNode root)

2 사고방식


두 갈래 나무를 반전시키다.귀속과 비귀속 두 가지 방법으로 풀 수 있다.
  • 귀속 방법은 쓰기가 매우 간결하고 다섯 줄 코드가 완성되어 현재 좌우 노드를 교환하고 귀속을 직접 호출하면 된다
  • 비귀속 방법은 나무의 층계를 참고하여 두루 훑어본다Queue 보조하기 위해 먼저 뿌리 노드를 대열에 배열한 다음에 대열에서 꺼내서 좌우 노드를 교환하고 존재하면 각각 좌우 노드를 대열에 배열한다. 이런 식으로 대열에 노드가 있을 때까지 순환을 멈추고 루트로 돌아가면 된다

  • 복잡도: 두 가지 방법의 시간과 공간 복잡도와 마찬가지로 Time O(n).Space O(n)

    3 코드

  • 사고방식1:
            public TreeNode invertTree(TreeNode root) {
    		if (root == null)
    			return root;
    		TreeNode tmp = root.left;
    		root.left = invertTree(root.right);
    		root.right = invertTree(tmp);
    		return root;
    	}

  • 4 총결산


    두 갈래 나무의 범람을 고찰하다.비귀속의 실현, 복습.비귀속을 실현하십시오.

    5 참조

  • leetcode
  • [LeetCode] 인버트 바이너리 트리 두 갈래 나무 뒤집기.
  • Reverse A Binary Tree (Left to Right)
  • 좋은 웹페이지 즐겨찾기