剑指offer39 平衡二叉树

剑指offer

39 平衡二叉树

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

输入

{1,2,3,4,5,6,7}

输出

true

思路（递归）

从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，则直接停止遍历，这样至多只对每个结点访问一次。

代码

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return TreeDepth(root) != -1; 
    }

    public static int TreeDepth(TreeNode root){
        if(root==null)return 0;

        //递归
        int depleft = TreeDepth(root.left);
        if(depleft==-1) return -1;    //如果递归完左子树，发现左子树不满足平衡二叉树，则返回 -1；右子树同理
        int depright = TreeDepth(root.right);
        if(depright==-1) return -1;
        return Math.abs(depleft-depright)>1 ? -1 : 1 + Math.max(depleft,depright);    //记得加上根节点的1
    }
}

补充：二叉树的创建、遍历、深度、宽度

其中，遍历包括 先序、中序、后序、层次，每一种都采用递归和非递归方法实现。

二叉树创建

采用 动态代理 方便输出，注意以下三点：

• 一个方法不能修改一个基本数据类型的参数
• 一个方法可以修改一个对象参数的状态
• 一个方法不能实现让对象参数引用一个新对象（这句话在这里尤为适用）

遍历

• 前序、中序、后序非递归遍历采用栈辅助实现
• 层次非递归遍历采用队列实现

代码

AbstractBinaryTree.interface

public interface AbstractBinaryTree {

    void printPostOder();

    void printPostOderByRecursion();

    void printPreOder();

    void printPreOderByRecursion();

    void printInOderByRecursion();

    void printInOder();

    void printHeight();

    void printMaxWidth();

    void printLevelOrder();

}

BinaryTree.java

package test.tree;

/**
 * 为了方便展示,并没有将Node属性私有
 */

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 为了方便展示,并没有将Node属性私有
 */

class Node {

    public String data;
    public Node left = null;
    public Node right = null;
    public boolean flag;

    Node(String data) {
        this.data = data;
    }

    Node() {
    }

    @Override
    public String toString() {

        return this.data;
    }

}



public class BinaryTree implements AbstractBinaryTree{

    private Node root = new Node();

    public Node getRoot() {
        return root;
    }

    public void printNode(Node node) {

        if (node.data == null) {
            System.out.print("");
        } else {
            System.out.print(node.data);
        }
    }

    public BinaryTree(String tree) {
        String[] treeNodes = tree.split(",");
        createTreeByRecursion(treeNodes);
    }

    private int createTreeByRecursion(Node node, String[] treeNodes, int n) {

        if ("#".equals(treeNodes[n]))
            return n + 1;

        node.data = treeNodes[n];

        node.left = new Node();
        int left = createTreeByRecursion(node.left, treeNodes, n + 1);

        node.right = new Node();
        int right = createTreeByRecursion(node.right, treeNodes, left);

        return right;
    }

    public void createTreeByRecursion(String[] treeNodes) {
        createTreeByRecursion(root, treeNodes, 0);
    }

    /**
     * 先序非递归创建
     */
    public void createTree(String[] treeNodes) {

        Stack<Node> stack = new Stack<>();

        int index = 0;

        Node node = root;

        while (index < treeNodes.length) {

            while (true) {

                if ("#".equals(treeNodes[index])) {

                    node = stack.pop();

                    if (node.flag == false) {
                        node.left = null;
                        node.flag = true;
                        stack.push(node);
                    } else {
                        node.right = null;
                    }

                    // 记得加1
                    index++;
                    break;
                }

                if (node.flag == true) {
                    node.right = new Node();
                    node = node.right;
                }

                node.data = treeNodes[index];
                stack.push(node);
                node.left = new Node();
                node = node.left;
                index++;
            }

            if (node.flag == false) {
                stack.push(node);
                node.flag = true;
                node = node.right;
            } else {
                node = stack.peek();
                node.flag = true;
            }

        }

    }

    // 递归调用的方法,需要将root传递进去
    //递归， 先序遍历
    private void printPreOderByRecursion(Node node) {

        if (node == null)
            return;

        printNode(node);
        printPreOderByRecursion(node.left);
        printPreOderByRecursion(node.right);

    }

    public void printPreOderByRecursion() {

        printPreOderByRecursion(root);
    }

    //递归， 中序遍历
    private void printInOderByRecursion(Node node) {

        if (node == null)
            return;

        printInOderByRecursion(node.left);
        printNode(node);
        printInOderByRecursion(node.right);

    }

    public void printInOderByRecursion() {
        printInOderByRecursion(root);
    }

    //递归， 后序遍历
    private void printPostOderByRecursion(Node node) {

        if (node == null)
            return;

        printPostOderByRecursion(node.left);
        printPostOderByRecursion(node.right);
        printNode(node);

    }

    public void printPostOderByRecursion() {

        printPostOderByRecursion(root);
    }

    // 非递归遍历二叉树

    // 先序遍历
    public void printPreOder() {

        Stack<Node> stack = new Stack<>();

        Node tempNode = root;

        while (true) {

            while (tempNode != null) {
                printNode(tempNode);
                stack.push(tempNode);
                tempNode = tempNode.left;
            }

            if (stack.isEmpty()) {
                break;
            }

            tempNode = stack.pop();
            tempNode = tempNode.right;

        }

    }

    // 中序遍历
    public void printInOder() {

        Stack<Node> stack = new Stack<>();

        Node tempNode = root;

        while (true) {

            while (tempNode != null) {
                stack.push(tempNode);
                tempNode = tempNode.left;
            }

            if (stack.isEmpty()) {
                break;
            }
            tempNode = stack.pop();
            printNode(tempNode);
            tempNode = tempNode.right;

        }

    }

    // 后序遍历
    public void printPostOder() {

        Stack<Node> stack = new Stack<>();

        Node tempNode = root;

        while (true) {

            while (tempNode != null) {
                if (tempNode.flag == true) {
                    tempNode = tempNode.right;
                } else {
                    stack.push(tempNode);
                    tempNode = tempNode.left;
                }

            }

            tempNode = stack.pop();

            if (tempNode.flag == false) {
                stack.push(tempNode);
                tempNode.flag = true;
                tempNode = tempNode.right;
            } else {
                printNode(tempNode);
                if (stack.isEmpty()) {
                    break;
                }
                tempNode = stack.peek();
                tempNode.flag = true;
            }

        }

    }

    // 层序遍历 利用队列
    public void printLevelOrder() {

        Queue<Node> queue = new LinkedList<>();

        Node tempNode = root;

        queue.offer(tempNode);

        while (!queue.isEmpty()) {

            Node topNode = queue.poll();

            if (topNode == null)
                continue;

            printNode(topNode);
            queue.offer(topNode.left);
            queue.offer(topNode.right);

        }

    }

    // 树高    递归，分别求出左子树的深度、右子树的深度，两个深度的较大值+1
    public int getHeightByRecursion(Node node) {

        if (node == null) {
            return 0;
        }
        int left = getHeightByRecursion(node.left);
        int right = getHeightByRecursion(node.right);
        return 1 + Math.max(left, right);

    }

    /**
     * 为什么不直接写成调用 root,而是另写一个方法去调用呢 因为,这样可以不再为root,单独设置一个临时变量去存贮
     * 而且也固定外部调用的方法,而不用关心内部的实现
     */

    public void printHeight() {

        int height = getHeightByRecursion(root);

        System.out.print(height);
    }

    // 利用层序遍历,得到树的最大宽度
    public void printMaxWidth() {

        Queue<Node> queue = new LinkedList<>();
        Queue<Node> queueTemp = new LinkedList<>();

        int maxWidth = 1;

        Node tempNode = root;

        queue.offer(tempNode);

        while (!queue.isEmpty()) {

            while (!queue.isEmpty()) {

                Node topNode = queue.poll();

                if (topNode == null)
                    continue;

                if (topNode.left.data != null) {

                    queueTemp.offer(topNode.left);
                }

                if (topNode.right.data != null) {

                    queueTemp.offer(topNode.right);
                }

            }

            maxWidth = Math.max(maxWidth, queueTemp.size());
            queue = queueTemp;
            queueTemp = new LinkedList<>();
        }

        System.out.print(maxWidth);
    }

}

BinaryTreeTest

package test.tree;

import java.lang.reflect.Proxy;

public class BinaryTreeTest {

    public static void main(String[] args) {
        String treeStr = "1,2,3,4,5,#,#,#,#,6,#";

        AbstractBinaryTree binaryTree =  BinaryTreeTest.proxyBinaryTree(treeStr);

        binaryTree.printPreOder();
        binaryTree.printPreOderByRecursion();
        binaryTree.printInOderByRecursion();
        binaryTree.printInOder();
        binaryTree.printPostOder();
        binaryTree.printPostOderByRecursion();
        binaryTree.printLevelOrder();
        binaryTree.printHeight();
        binaryTree.printMaxWidth();
    }

    public static AbstractBinaryTree proxyBinaryTree(String treeStr) {

        AbstractBinaryTree binaryTree = new BinaryTree(treeStr);

        Object newProxyInstance = Proxy.newProxyInstance(binaryTree.getClass().getClassLoader(),
                binaryTree.getClass().getInterfaces(), (proxy, method, args) -> {
                    System.out.println(method.getName());
                    Object invoke = method.invoke(binaryTree, args);
                    System.out.println();
                    return invoke;
                });

        return (AbstractBinaryTree) newProxyInstance;
    }

}