85.Insert Node in a Binary Search Tree-在二叉查找树中插入节点（容易题）

本文主要是介绍85.Insert Node in a Binary Search Tree-在二叉查找树中插入节点（容易题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在二叉查找树中插入节点

题目

给定一棵二叉查找树和一个新的树节点，将节点插入到树中。

你需要保证该树仍然是一棵二叉查找树。
样例

给出如下一棵二叉查找树，在插入节点6之后这棵二叉查找树可以是这样的：
挑战

能否不使用递归？
题解

二叉查找树中任意节点的键值都大于它左子树中任意节点的键值，都小于它右子树中任意节点的键值，且不含有相同键值的节点。

1.递归法

/*** Definition of TreeNode:* public class TreeNode {*     public int val;*     public TreeNode left, right;*     public TreeNode(int val) {*         this.val = val;*         this.left = this.right = null;*     }* }*/
public class Solution {/*** @param root: The root of the binary search tree.* @param node: insert this node into the binary search tree* @return: The root of the new binary search tree.*/public TreeNode insertNode(TreeNode root, TreeNode node) {if (root != null){if (root.val < node.val){root.right = root.right == null ? node : insertNode(root.right,node);}else{root.left = root.left == null ? node : insertNode(root.left,node);}}return root == null ? node : root;}
}

2.非递归法

/*** Definition of TreeNode:* public class TreeNode {*     public int val;*     public TreeNode left, right;*     public TreeNode(int val) {*         this.val = val;*         this.left = this.right = null;*     }* }*/
public class Solution {/*** @param root: The root of the binary search tree.* @param node: insert this node into the binary search tree* @return: The root of the new binary search tree.*/public TreeNode insertNode(TreeNode root, TreeNode node) {TreeNode result = root;while (result != null){if (result.val < node.val){if (result.right == null){result.right = node;return root;}result = result.right;}else{if (result.left == null){result.left = node;return root;}result = result.left;}}return root == null ? node : root;}
}