leetcode 문제 풀기_OJ 226 반전 두 갈래 나무

1444 단어 leetcode
Invert a binary tree.
Example:
Input:
     4    / \  2     7  /\ /\1   3 6   9 Output:
4/\72/\/\9 6 3 1 문제 풀이 사고방식: 즉, 원래 두 갈래 나무의 거울을 구하는 것이기 때문에 각 층의 좌우 노드를 반대로 하고 좌우 자수를 반대로 하면 된다. 귀속은 다음과 같다.
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode temp=root.left;
        root.left=invertTree(root.right);
        root.right=invertTree(temp);
        return root;
    }
}

반복적인 실현 사고방식도 번거롭지 않다. 주로 하나의 대기열로 과정에서 조작할 노드(선진 선출)를 저장하고 루트, 교환 후의 좌우 노드를 순서대로 눌러서 마지막에 되돌아오는 것도 원래 두 갈래 나무의 거울이다.
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return root;
        Queue queue = new LinkedList();
        queue.offer(root);// add , offer false,add 
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();// remove , poll null,remove 
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
        return root;
    }
}

좋은 웹페이지 즐겨찾기