对一个二叉树，如何判断二叉树是否平衡、中序遍历、翻转？写出实

[问答题]

对一个二叉树，如何判断二叉树是否平衡、中序遍历、翻转？写出实现代码，并分析时间、空间复杂度。

pein531

平衡二叉树直接检查左右子树的高度差是否小于等于1，这里给出Java实现代码

class TreeNode {
    TreeNode (int val){
        root.val = val;
        root.left = null;
        root.right = null;
    }
}

public class Solution {
    // 求树的深度
    public int TreeDepth(TreeNode node) {
        if(root == null) return 0;
        // 计算左子树高度
        int left = TreeDepth(node.left);
        // 计算右子树高度
        int right = TreeDepth(node.right);
        // 两个较大的值就是树的深度
        return 1 + (left > right? left : right);
    }
    
    // 判断平衡二叉树
    public boolean isBalancedTree(TreeNode root) {
        if(root == null) return true;
        if(Math.abs(TreeDepth(root.left) - TreeDepth(root.right)) > 1)
            return false;
        return true;
    }
}

中序遍历给出递归版代码，因为是要遍历每一个节点，所以时间复杂度为O(n)，递归消耗栈空间，空间复杂度也为O(n)

public void inOrder(TreeNode root, ArrayList<Integer> list) {
    if(root == null) return;
    inOrder(root.left, list);
    list.add(root.val);
    inOrder(root.right, list);
}

反转二叉树仍然采用递归进行实现，自底向上在每一层交换左右子树

public void Mirror(TreeNode node) {
    if(node != null) {
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        Mirror(node.left);
        Mirror(node.right);
    }
}

发表于 2020-10-31 10:58:29 回复(0)