二叉树算法题

树的初始化

类包含左右节点属性以及val值。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

二叉树的中序遍历。

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        dfs(res,root);
        return res;
    }

    void dfs(List<Integer> res, TreeNode root) {
        if(root==null) {
            return;
        }
        //按照 左-打印-右的方式遍历
        dfs(res,root.left);
        res.add(root.val);
        dfs(res,root.right);
    }

二叉树的中序遍历2。

    public static List<Integer> inorderTraversal2(TreeNode root){//中序遍历
        List<Integer> res = new ArrayList<>();
        Deque<Object> stack = new LinkedList<>();
        if(root == null) return res;
        stack.push("WHITE");
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = (TreeNode)stack.pop();
            String color = (String)stack.pop();
            if (node == null) continue;
            if(color == "WHITE"){
                stack.push("WHITE");
                stack.push(node.right);
                stack.push("GRAY");
                stack.push(node);
                stack.push("WHITE");
                stack.push(node.left);
            }else{
                res.add(node.val);
            }
        }
        return res;
    }

翻转二叉树。

    public static TreeNode invertTree(TreeNode root) {
        //递归函数的终止条件，节点为空时返回
        if(root==null) {
            return null;
        }
        //下面三句是将当前节点的左右子树交换
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = tmp;
        //递归交换当前节点的 左子树
        invertTree(root.left);
        //递归交换当前节点的 右子树
        invertTree(root.right);
        //函数返回时就表示当前这个节点，以及它的左右子树
        //都已经交换完了
        return root;
    }

二叉树的最大深度

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }

    }

测试类 生成了7种不一样的树。

    public static void main(String[] args) {//7个不同的树
        TreeNode root1 = null; // 空树
        TreeNode root2 = new TreeNode(1); // 只有根节点的树
        TreeNode root3 = new TreeNode(1); // 完全平衡二叉树
        root3.left = new TreeNode(2);
        root3.right = new TreeNode(3);
        root3.left.left = new TreeNode(4);
        root3.left.right = new TreeNode(5);
        TreeNode root4 = new TreeNode(1); // 非平衡二叉树
        root4.left = new TreeNode(2);
        root4.left.left = new TreeNode(3);
        root4.left.left.left = new TreeNode(4);
        root4.left.left.left.left = new TreeNode(5);
        TreeNode root5 = new TreeNode(1); // 只有左子树的树
        root5.left = new TreeNode(2);
        TreeNode root6 = new TreeNode(1); // 只有右子树的树
        root6.right = new TreeNode(2);
        TreeNode root7 = new TreeNode(1); // 多层深度的树
        root7.left = new TreeNode(2);
        root7.right = new TreeNode(3);
        root7.left.left = new TreeNode(4);
        root7.right.right = new TreeNode(5);
        invertTree(root7);
        System.out.println(inorderTraversal2(root7));
    }