二叉树--经典面试题2

目录

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

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

3.二叉树创建字符串

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

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

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

7.二叉树的最大宽度

8.合并二叉树

---

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

• 题目描述

•  代码

    //前序遍历的下标放在外面，防止在建左树的时候，递出去++，归回来又变成原来的值了
    public int preIndex = 0;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend) {
        if(inbegin > inend) return null;
 
        TreeNode root = new TreeNode(preorder[preIndex]);
        //找根节点在中序遍历的位置
        int rootPos = findInorderPos(inorder, inbegin, inend, preorder[preIndex]);
        preIndex++;
 
        root.left = buildTreeChild(preorder, inorder, inbegin, rootPos - 1);
        root.right = buildTreeChild(preorder, inorder, rootPos + 1, inend);
 
        return root;
    }
    private int findInorderPos(int[] inorder, int inbegin, int inend, int val) {
        for(int i = inbegin; i <= inend; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder, inorder, 0, inorder.length-1);
    }

• 图解

•  思路

1.定义 preIndex 遍历前序遍历这个数组

2.在中序遍历的 ib - ie 之间，找到 ri 的下标位置

3.此时 ri 左边的就是左树，ri 右边的就是右树

4.递归创建左树和递归创建右树

5.当 ib > ie 的时候，说明没有了左树或者右树

当然这种做法在oj 能跑过，但时间复杂度还是过高了，等我学完哈希map回过头来优化代码，，，

---

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

• 题目描述

• 代码 

    public int postIndex = 0;
    //postIndex从后序遍历这个数组的最后开始，那么就是根，右，左
    public TreeNode buildTreeChild(int[] postorder, int[] inorder, int inbegin, int inend) {
        if(inbegin > inend) return null;
 
        TreeNode root = new TreeNode(postorder[postIndex]);
        //找根节点在中序遍历的位置
        int rootPos = findInorderPos(inorder, inbegin, inend, postorder[postIndex]);
        postIndex--;
 
        root.right = buildTreeChild(postorder, inorder, rootPos + 1, inend);
        root.left = buildTreeChild(postorder, inorder, inbegin, rootPos - 1);
 
        return root;
    }
    private int findInorderPos(int[] inorder, int inbegin, int inend, int val) {
        for(int i = inbegin; i <= inend; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;
        return buildTreeChild(postorder, inorder, 0, inorder.length-1);
    }

• 分析

这道题和上一道题是差不多的，只需要将前序遍历数组起初的下标改成这里后序遍历数组中的最后一个下标，因为后序遍历是左右根，所以从后面开始，就变了根左右，其余的思路都是一样的。

---

3.二叉树创建字符串

• 题目描述

• 代码 （建议跟着图解看这道题）

    public void tree2strChild(TreeNode cur, StringBuilder sb) {
        sb.append(cur.val);
        //先走左边
        if(cur.left != null) {
            sb.append("(");
            tree2strChild(cur.left, sb);
            sb.append(")");
        } else {
            if(cur.right == null) {
                return;
            } else {
                sb.append("()");
            }
        }
        //回退完了之后，再走右边
        if(cur.right == null) {
            return;
        } else {
            sb.append("(");
            tree2strChild(cur.right, sb);
            sb.append(")");
        }
    }
 
    public String tree2str(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        tree2strChild(root, sb);
        return sb.toString();
    }

•  图解

做这道题，如果看不懂题，必须要跟着例子图，走代码，请看下面图解：

首先要把几种情况分清楚：

 

---

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

• 代码

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
 
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        //这里是一个难点，需要倒回来写这个循环
        while(!stack.empty() || cur != null) {
            while(cur != null) {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }

• 图解

---

5.二叉树中序非递归遍历实现（与4相似）

• 代码

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
 
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
 
        while(!stack.empty() || cur != null) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);//先添加左
            cur = top.right;//判断以 cur.left 作为根的这棵树有没有右孩子
        }
        return list;
    }

• 图解

---

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

• 代码

      public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
 
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
 
        while(!stack.empty() || cur != null) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            //因为是 左 右 根 ，所以添加元素前需要判断一下是否已添加
            if(top.right == null || top.right == prev) {
                stack.pop();
                list.add(top.val);
                prev = top;//添加过的标记一下
            } else {
                cur = top.right;
            }
        }
        return list;
    }

这里要注意的是，因为 根 左 右 ，而每次循环都把左右子树当成根了，那么添加结点的时候，就会出现这样一个问题：

所以这个题的难点就是每次添加完一个结点后需要记录一下！！！

---

7.二叉树的最大宽度

• 题目描述

假说 ：

从题目描述和例子来看，如果这棵二叉树是按照层序遍历来编号，最大宽度似乎就是求每一层最右边结点编号减去最左边结点编号的差值+1，然后取其中的最大值。

• 代码 （dfs）

    //最大宽度必须定义在外面，否则每次递归都重新定义了
    int maxW;
    public int widthOfBinaryTree(TreeNode root) {
        int index = 1;//值
        int level = 1;//层数
        dfs(root,1,1,new ArrayList<>());
        return maxW;   
    }
    private void dfs(TreeNode root, int level, int index, List<Integer> leftList) {
        if(root == null) return;
        //层数大于集合元素个数，就添加-->即添加所有最左边元素
        if(level > leftList.size()) {
            leftList.add(index);
        }
        //所有除了最左边结点减去最左边的结点的差值加一就等于两者之间的宽度，不断筛选最大的宽度
        maxW = Math.max(maxW,index - leftList.get(level - 1) + 1);
        //注意index可不敢++
        dfs(root.left, level + 1, index * 2, leftList);
        dfs(root.right, level + 1, index * 2 + 1, leftList);
    }

•  图解

---

8.合并二叉树

• 题目描述

•  代码

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) {
            return root2;
        }
        if(root2 == null) {
            return root1;
        }
        TreeNode newRoot = new TreeNode(root1.val + root2.val);
        newRoot.left = mergeTrees(root1.left,root2.left);//新的左子树
        newRoot.right = mergeTrees(root1.right,root2.right);//新的右子树
        return newRoot;
    }

• 思路

1.在递归的过程中，当一棵树为空树时，直接返回另一棵树的根；

2.如果两树的根都不为空，新的根的值就是两树根值的和。

谢谢观看！！！