编号226:翻转二叉树

编号226:翻转二叉树

翻转一棵二叉树。

编号226:翻转二叉树

思路:

要实现反转,就是要把每个结点的左右孩子交换一下(孩子下面的结点是一起交换的),需要的是遍历的顺序,递归的中序遍历的方法不可以实现,因为会交换两次。

//利用前序遍历递归实现
public static Node reverseTree(Node root){
        if(root == null){
            return null;
        }
        swap(root.left,root.right);//中
        reverseTree(root.left);//左
        reverseTree(root.right);//右
        
        return root;
    }
//利用迭代实现
public static Node reverseTree2(Node root){
        if(root == null){
            return root;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            //交换左右子树
            Node node = stack.pop();
                Node 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);
            }

        }
        return root;
    }
//利用层序遍历使用
public Node levelOrder(Node root) {

        if (root == null) {
            return null;
        }
        //创建优先级队列
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-->0){
                //将当前元素的非空子节点压入队列
                Node temp = queue.poll();
                swap(temp.left,temp.right);
                if (temp.left != null) {
                    queue.add(temp.left);
                }
                if (temp.right != null) {
                    queue.add(temp.right);
                }
            }

        }
        return root;
    }

上一篇:02 ILRT的基础使用


下一篇:UnityILRuntime使用UnityWebRequest加载Dll文件