力扣.623. 在二叉树中增加一行(链式结构的插入操作)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int targetVal;
private int targetDepth;
private int curDepth = 0;
public TreeNode addOneRow(TreeNode root, int val, int depth) {
targetDepth = depth;
targetVal = val;
// Insert into the first line with special treatment
if (targetDepth == 1) {
TreeNode newRoot = new TreeNode(val);
newRoot.left = root;
return newRoot;
}
// Walk through the binary tree and insert the corresponding row
traverse(root);
return root;
}
private void traverse(TreeNode root) {
if (root == null) {
return;
}
curDepth++;
if (curDepth == targetDepth - 1) {
TreeNode newLeftNode = new TreeNode(targetVal);
TreeNode newRightNode = new TreeNode(targetVal);
newLeftNode.left = root.left;
newRightNode.right = root.right;
root.left = newLeftNode;
root.right = newRightNode;
}
traverse(root.left);
traverse(root.right);
curDepth--;
}
}