美文网首页
二叉树的镜像

二叉树的镜像

作者: 6默默Welsh | 来源:发表于2018-02-07 15:02 被阅读7次

    描述

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

                8
               /  \
              6   10
             / \  / \
            5  7 9 11
            镜像二叉树
                8
               /  \
              10   6
             / \  / \
            11 9 7  5
    

    代码

    1. 递归
    /**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
        }
    }
    */
    
    public class Solution {
        public void Mirror(TreeNode root) {
            if (root == null) {
                return;
            }
            
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            
            Mirror(root.left);
            Mirror(root.right);
        }
    }
    
    1. 非递归用栈
    import java.util.Stack;
    /**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    
    public class Solution {
        public void Mirror(TreeNode root) {
            if (root == null) {
                return;
            }
            
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            
            while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                
                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;
                
                if (node.left != null) {
                    stack.push(node.left);
                }
                if (node.right != null) {
                    stack.push(node.right);
                }
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:二叉树的镜像

          本文链接:https://www.haomeiwen.com/subject/ipzozxtx.html