Dowemo
0 0 0 0

Given the root of a binary tree, then value v and depth d you need to add a row of node with value v at the given depth d_ the _ root _ is _ at _ depth 1.

The add rule is: given a positive integer depth d for each not null tree node N in depth D-1 Create two tree node with value v as N 's Left subtree root and right subtree root. And. N 'soriginal left subtreeShould be the left subtree of the new left subtree root, its original right subtreeShould be the right subtree of the new right subtree root. If depth. dA is 1 that means there's no depth d-1 at all, then create a tree node with vAs the new root of the whole original, and the original tree is the new root.

示例1:

Input: 
A binary tree as following:
 4
/
 2 6
//
 3 1 5 v = 1d = 2Output: 
 4
/
 1 1
/
 2 6
//
 3 1 5 

示例2:

Input: 
A binary tree as following:
 4
/
 2 
/
 3 1 v = 1d = 3Output: 
 4
/
 2
/
 1 1
/
3 1

注:

  • Maximum depth of the given tree + 1 ] the given d is in range [ 1.
  • The given binary tree has at least one tree node.


  • It should be nice to walk through the first order, and if the current layer is already a target layer, then don't go to its child node.
    Note that when you go to the d layer, you need to adjust the tree. For example, the second example, d = 3, when you go to 2 this node, depth = 2, which means that you want to insert two target nodes at the bottom of the current node. Look at the code.
    Code:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 private int targetDepath = -1;
 private int value = -1;
 public TreeNode addOneRow(TreeNode root, int v, int d) {
 if(d <0) return root;
 if(d == 1) {
 TreeNode newRoot = new TreeNode(v);
 newRoot.left = root;
 return newRoot;
 }
 targetDepath = d;
 value = v;
 preOrder(root, null, 1);
 return root;
 }
 private void preOrder(TreeNode node, String direction, int layer) {
 if(node == null) return;
 if(layer + 1 == targetDepath) {
 TreeNode leftNode = new TreeNode(value);
 TreeNode rightNode = new TreeNode(value);
 leftNode.left = node.left;
 rightNode.right = node.right;
 node.left = leftNode;
 node.right = rightNode;
 } else if(layer> targetDepath) return;
 else {
 preOrder(node.left,"L", layer + 1);
 preOrder(node.right,"R", layer + 1);
 }
 }
}





Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs