二叉树镜像Java-剑指offer+二叉树插入节点

偏执的太偏执、 2024-04-17 17:51 63阅读 0赞

## 题目描述 ##

操作给定的二叉树，将其变换为源二叉树的镜像。

## 解题思路 ##

1、递归方法实现：先判断是否为空，或者左右节点为空，这种直接return；如果不为空直接左右节点交换，交换直接递归交换根节点的左节点，再递归交换根节点的右节点；直到遍历左右节点。

2、栈的实现：利用栈的先进后出的特性进行实现。

将根节点push到栈中，如果栈不为空，先pop根节点，然后进行交换；再遍历交换左节点，交换；再遍历右节点交换；

1、递归实现

> 1.  /\*\*
> 2.  public class TreeNode \{
> 3.      int val = 0;
> 4.      TreeNode left = null;
> 5.      TreeNode right = null;
> 6.      public TreeNode(int val) \{
> 7.          this.val = val;
> 8.      \}
> 9.  \}
> 10. \*/
> 11. public class Solution \{
> 12.     public void Mirror(TreeNode root) \{
> 13.         TreeNode temp;
> 14.         if(root==null) return;
> 15.         if(root.left == null && root.right==null) return;
> 16.         if(root != null)\{
> 17.             temp = root.left;
> 18.             root.left = root.right;
> 19.             root.right = temp;
> 20.         \}
> 21.         if(root.left != null)
> 22.             Mirror(root.left);
> 23.         if(root.right != null)
> 24.             Mirror(root.right);
> 25.     \}
> 26. \}

2、栈实现

> 1.  import java.util.Stack;
> 2.  public class Solution \{
> 3.      public void Mirror(TreeNode root) \{
> 4.          TreeNode temp;
> 5.          if(root==null) return;
> 6.          if(root.left == null && root.right==null) return;
> 7.          Stack<TreeNode> stack = new Stack<TreeNode>();
> 8.          stack.push(root);
> 9.          while(!stack.isEmpty())\{
> 10.             TreeNode r = stack.pop();
> 11.             if(r.left != null || r.right != null)
> 12.             \{
> 13.                 temp = r.left;
> 14.                 r.left = r.right;
> 15.                 r.right = temp;
> 16.             \}
> 17.             if(r.left != null)
> 18.                 stack.push(r.left);
> 19.             if(r.right != null)
> 20.                 stack.push(r.right);
> 21.         \}
> 22.     \}
> 23. \}

二叉树插入节点

> 1.   //插入节点  
> 2.      public static void insertBSTNode(BSTNode root,Integer key)\{  
> 3.          BSTNode insertNode =new BSTNode(key);  
> 4.          while(root !=null)\{  
> 5.              if(key<root.getData())\{  
> 6.                  if(root.getLchild() !=null)\{  
> 7.                      root =root.getLchild();  
> 8.                  \}else\{  
> 9.                      root.setLchild(insertNode);  
> 10.                     return;  
> 11.                 \}  
> 12.             \}else if(key>root.getData())\{  
> 13.                 if(root.getRchild() !=null)\{  
> 14.                     root =root.getRchild();  
> 15.                 \}else\{  
> 16.                     root.setRchild(insertNode);  
> 17.                     return;  
> 18.                 \}  
> 19.             \}else\{  
> 20.                 throw new RuntimeException("插入节点值已经存在");  
> 21.             \}  
> 22.         \}  
> 23.     \}