数据结构青铜到王者第十二话---二叉树（4）

寻星探路

发布于 2025-12-17 18:31:41

400

一、二叉树的相关练习（续）

1、根据一棵树的前序遍历与中序遍历构造二叉树

直接去用一个新的函数作为返回值去执行操作，传入的信息分别表示前序序列、中序序列、当前子树在中序序列中的起始索引以及结束索引。判定是否是无效子树，再去根据先序序列创建根节点，再从中序遍历中找到根节点并进行记录，推动先序遍历进行并分别递归函数找到左右子树。

public TreeNode buildTree(int[] preorder, int[] inorder) {
       return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
 
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {
        //这种情况下 表明 当前root 没有子树了 
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        int rootIndex = findVal(inorder,inbegin,inend,preorder[preIndex]);
        preIndex++;
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }
    private int findVal(int[] inorder,int inbegin,int inend,int val) {
        for(int i = inbegin ;i <= inend;i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

2、根据一棵树的中序遍历与后序遍历构造二叉树

（106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode））

和上面一样的，直接到根据后序序列最后一个数据作为根节点，在中序遍历中找到根节点分好左右子树，再由左右子树进行递归实现整棵树

    public int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length-1;
        return buildTreeChild(inorder,postorder,0,inorder.length-1);
    }
 
    public TreeNode buildTreeChild(int[] inorder,int[] postorder,int inbegin,int inend) {
        //这种情况下 表明 当前root 没有子树了 
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
 
        int rootIndex = findVal(inorder,inbegin,inend,postorder[postIndex]);
        postIndex--;
        
        root.right = buildTreeChild(inorder,postorder,rootIndex+1,inend);
 
        root.left = buildTreeChild(inorder,postorder,inbegin,rootIndex-1);
       
        return root;
    }
    private int findVal(int[] inorder,int inbegin,int inend,int val) {
        for(int i = inbegin ;i <= inend;i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

3、二叉树创建字符串

（606. 根据二叉树创建字符串 - 力扣（LeetCode））

先判空。再去判断左右子树是否均为空。第三种情况，判断只有左子树，直接进行连接并添加节点数值，添加括号的同时再递归处理左子树。若是均存在则再上一个的基础上多加一个递归右子树，往复操作即可

class Solution {
    public String tree2str(TreeNode root) {
        if (root == null) {
            return "";
        }
        if (root.left == null && root.right == null) {
            return Integer.toString(root.val);
        }
        if (root.right == null) {
            return new StringBuffer().append(root.val).append("(").append(tree2str(root.left)).append(")").toString();
        }
        return new StringBuffer().append(root.val).append("(").append(tree2str(root.left)).append(")(").append(tree2str(root.right)).append(")").toString();
    }
}

4、二叉树前序非递归遍历实现

（144. 二叉树的前序遍历 - 力扣（LeetCode））

我们也可以用迭代的方式实现方法一的递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同，具体可以参考下面的代码。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return res;
    }
}

5、二叉树中序非递归遍历实现

（94. 二叉树的中序遍历 - 力扣（LeetCode））

递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同，具体实现可以看下面的代码。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stk = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

6、二叉树后序非递归遍历实现

（145. 二叉树的后序遍历 - 力扣（LeetCode））

我们也可以用迭代的方式实现递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同，具体可以参考下面的代码。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-09-03，如有侵权请联系 cloudcommunity@tencent.com 删除

root