Leetcode623. 두 갈래 나무에 한 줄 추가

8831 단어 Leetcode

Leetcode623. 두 갈래 나무에 한 줄 추가


비슷한 제목: Leetcode104.두 갈래 나무의 최대 깊이 제목: 두 갈래 나무를 정하고 뿌리 노드는 1층, 깊이는 1이다.d층에 v의 노드를 추가합니다.규칙 추가: 깊이 d(정수)를 지정하고 깊이 d-1층의 모든 비공식 노드 N에 대해 N에 대한 두 개의 값이 v인 왼쪽 트리와 오른쪽 트리를 생성합니다.N의 원래 왼쪽 트리를 새 노드 v의 왼쪽 트리로 연결합니다.N의 원래 오른쪽 트리를 새 노드 v의 오른쪽 트리로 연결합니다.만약 d의 값이 1이고 깊이 d-1이 존재하지 않는다면, 새로운 루트 노드 v를 만듭니다. 원래의 전체 나무는 v의 왼쪽 트리가 됩니다.
예 1:
 : 
 :
       4
     /   \
    2     6
   / \   / 
  3   1 5   
v = 1
d = 2
 : 
       4
      / \
     1   1
    /     \
   2       6
  / \     / 
 3   1   5   

  2:
 : 
 :
      4
     /   
    2    
   / \   
  3   1    
v = 1
d = 3
 : 
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1

문제: 각 층의 깊이를 계산하고 교체를 사용합니다.java 코드:
/**
     * @param root
     * @param v
     * @param d
     * @return
     */
    public static TreeNode addOneRow(TreeNode root, int v, int d) {
        if (d == 1) {
            TreeNode node = new TreeNode(v);
            node.left = root;
            return node;
        } else {
            Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
            queue.add(new Pair<>(root, 1));
            while (!queue.isEmpty()) {
                Pair<TreeNode, Integer> pair = queue.poll();
                TreeNode treeNode = pair.getKey();
                Integer depth = pair.getValue();

                if (depth == d - 1) {
                    TreeNode left = treeNode.left;
                    TreeNode right = treeNode.right;

                    treeNode.left = new TreeNode(v);
                    treeNode.right = new TreeNode(v);
                    treeNode.left.left = left;
                    treeNode.right.right = right;
                } else {
                    if (treeNode.left != null) {
                        queue.add(new Pair<>(treeNode.left, depth + 1));
                    }
                    if (treeNode.right != null) {
                        queue.add(new Pair<>(treeNode.right, depth + 1));
                    }
                }
            }
            return root;
        }
    }

좋은 웹페이지 즐겨찾기