L1-在二叉查找树中插入节点

Posted on | In |

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

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

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

2 2
/ \ / \
1 4 –> 1 4
/ / \
3 3 6

挑战
能否不使用递归？

非递归解法

让一个节点指向root，比根节点的值小往左走，否则往右走。
注意走的时候 先判断根左边或右边的节点是否为空 如果为空则直接插入 否则继续走。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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)
			return node;
		TreeNode t = root;
		while (t != null) {
			if (node.val < t.val) {
				if (t.left == null)
				{
				    t.left = node;
					return root;
				}
				else {
					t = t.left;
					continue;
				}
			}
			if (node.val > t.val) {
				if (t.right == null)
					{
					    t.right = node;
			            return root;
					}
				else {
					t = t.right;
					continue;
				}
			}
		}
		return root;
	}

}

递归解法

利用二叉查找树的特性，根据插入节点的值和根节点的值进行比较，若比根节点的值小则在根的左子树上插入，否则在右子树上插入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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) {
        // write your code here
        if(root==null) root=node;
        if(node.val<root.val)
        root.left=insertNode(root.left,node);
        if(node.val>root.val)
        root.right=insertNode(root.right,node);
        return root;
    }
}