数据结构：二叉树—面试题（二）

1、二叉树的最近公共祖先

习题链接https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

描述：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

解题思路

对于这道题我们有两种思路来解决这个问题

思路一：

首先，我们要去找到p,q这两个结点，我们从根节点开始找，如果根结点属于p或者q，我们就直接返回，此时的根结点就是p,q的最近公共祖先。

但我们的根节点不是p,q我们就去根的左子树和右子树去找，如果根的左右两个结点还不是，我们就继续向下找，因此我们需要利用递归实现。

到最后了我们还是没有找到，我们就返回null，如果找到了就返回p或者q的结点，当我们得到了p和q这俩个结点后，还要得到最近的公共祖先，如果这两个返回值不为空，就返回root（此时递归回来两个结点的父节点），如果一个为空一个不为空就返回不为空的结点。

思路二：

首先，我们还是从根结点开始找，如果根结点属于p或者q，我们就直接返回，此时的根结点就是p,q的最近公共祖先。

但如果我们的根节点不是，我们就创建两个栈，将从根节点到p的结点放到stack1这个栈中，将从根节点到q的结点放到stack2中。

首先我们从根节点开始放，如果不是就走左子树，走完左子树再走右子树，走一个结点就入栈一个，如果在递归往下走的过程中，如果此时是左边为空，就返回false，然后就向右边走，如果右边也为空就弹出这个结点，并返回false,如果最后, 如果左右两边找到了就返回true.

最后我们得到的两个栈，存放的就是从根节点到p,q的所有结点，此时我们计算栈的长度，求出差值，如果一个栈长，就让这个栈弹出差值个元素，让这两个栈是相同的长度，然后让这两个栈一起走，如果在走的过程中他们相遇了此时相遇的值就是我们的p,q最近公共祖先。

完整代码 

思路一:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(root == p || root == q){
            return root;
        }
        TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
        if(leftNode != null && rightNode != null){
            return root;
        }else if(leftNode != null){
            return leftNode;
        }else if(rightNode != null){
            return rightNode;
        }
        return null;
    }
}

思路二： 

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       if(root == null){
        return null;
       }
       if(root == p || root == q){
        return root;
       }
       Stack<TreeNode> stack1 = new Stack<>();
       Stack<TreeNode> stack2 = new Stack<>();

       TreeNodeStack(root,p,stack1);
       TreeNodeStack(root,q,stack2);
       int size = stack1.size() - stack2.size();
       if(size < 0){
        size = Math.abs(size);
        while(size != 0){
            stack2.pop();
            size--;
        }
       }else{
         while(size != 0){
            stack1.pop();
            size--;
         }
        }
        while(!stack1.isEmpty() && !stack2.isEmpty()){
           if(stack1.peek() != stack2.peek()){
            stack1.pop();
            stack2.pop();
           }else{
            return stack1.pop();
           }
        }
        return null;
    }

    public boolean TreeNodeStack(TreeNode root,TreeNode node,Stack<TreeNode> stack){
        if(root == null){
            return false;
        }
        stack.add(root);
        if(root == node){
            return true;
        }
        boolean flg = TreeNodeStack(root.left,node,stack);
        if(flg){
            return true;
        }
        flg = TreeNodeStack(root.right,node,stack);
        if(flg){
            return true;
        }
        stack.pop();
        return false;
    } 
}

2、从前序与中序遍历序列构建二叉树

习题链接https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

描述：

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

解题思路

他要我们根据前序和中序创建二叉树，首先，我们要创建一个变量preorderindex，作为一个引用指向前序遍历，并在设立两个变量inbegin和inend代表中序遍历的第一个和最后一个位置。

我们知道，我们前序遍历的第一个结点就是我们的根节点，此时我们在去中序遍历中找这个节点，此时在中序遍历中这个结点的左边就是我们的左子树的所有结点，右边是我们右子树的所有结点。

而我们左子树的第一个结点就是我们前序遍历的第二个结点，而我们左子树要在中序遍历找的范围就是我们的最左边inbegin和我们的根节点的位置减一，而我们右子树要在中序遍历找的范围就是我们的最右inend和我们的根节点的位置加一，每创建一个结点就让preorderindex++。

最后一点我们什么时候什么时候停止创建，就是我们中序遍历中的inbegin和inend相遇了或者inbegin超过inend。

完整代码 

class Solution {
    public int preorderindex = 0;
    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) {
        if(inbegin > inend){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preorderindex]);
        int rootindex = findindex(inorder,inbegin,inend,preorder[preorderindex]);
        preorderindex++;
        root.left = buildTreeChild(preorder,inorder,inbegin,rootindex-1);
        root.right = buildTreeChild(preorder,inorder,rootindex+1,inend);
        return root;
    }

    public int findindex(int[] inorder,int inbegin,int inend,int key){
        for(int i = inbegin ;i<=inend;i++){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }
}

3、从中序与后序遍历序列构建二叉树

习题链接https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

描述：

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

解题思路

这道题和我们上面的方式是一样的，只是我们找根节点是从后序遍历的最后一个结点开始找，并且我们要先建立右子树在建立左子树，因为我们后序遍历的方式是左右根，我们根是跟着右树相连的。

完整代码 

class Solution {
    public int postorderindex =0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postorderindex =  postorder.length-1;
        return buildTreeChild(inorder,postorder,0,inorder.length-1);
    }

    public TreeNode buildTreeChild(int[] inorder, int[] postorder,int inbegin ,int inend) {
        if(inbegin > inend){
            return null;
        }
        TreeNode root = new TreeNode(postorder[postorderindex]);
        int rootindex = findindex(inorder,inbegin,inend,postorder[postorderindex]);
        postorderindex--;

        root.right = buildTreeChild(inorder,postorder,rootindex+1,inend);
        root.left = buildTreeChild(inorder,postorder,inbegin,rootindex-1);
       
        return root;
    }

    public int findindex(int[] inorder,int inbegin,int inend,int key){
        for(int i = inbegin;i<= inend;i++){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }
}

4、根据二叉树创建字符串

习题链接https://leetcode.cn/problems/construct-string-from-binary-tree/description/https://leetcode.cn/problems/construct-string-from-binary-tree/description/

描述：

给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。

空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

解题思路

根据这道题的示例，其实我们能发现他的创建规则。

首先我们先将根节点传入字符串中，然后如果左子树不为空就不断向下走左子树，每遇到一个左节点不为空的结点就先在字符串中添加一个左括号“（”，然后再利用递归添加这个结点的值，并不断的往下走如果我们的左节点为空了，但是右节点不为空就添加一个“（）”，如果左右都为空就直接返回，并利用递归添加一个“）”。

最后我们的左子树的结点已经全部添加到字符串上了，我们再去添加右子树，如果右子树不为空，我们还是去添加一个“（”，然后再去添加右子树的结点，如果最后最后右子树为空了，并且能走到右子树也代表左子树为空，此时就直接返回并利用递归添加一个“）”。

完整代码 

class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }

    public void tree2strChild(TreeNode root,StringBuilder stringBuilder) {
       if(root == null){
            return ;
       }
       stringBuilder.append(root.val);
       if(root.left != null){
        stringBuilder.append("(");
        tree2strChild(root.left,stringBuilder);
        stringBuilder.append(")");
       }else{
        if(root.right != null){
            stringBuilder.append("()");
        }else{
            return ;
        }
       }

       if(root.right != null){
        stringBuilder.append("(");
        tree2strChild(root.right,stringBuilder);
        stringBuilder.append(")");
       }else{
         return;
       }

    }
}

5、二叉树的前序遍历

习题链接https://leetcode.cn/problems/binary-tree-preorder-traversal/description/https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

描述：

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

解题思路

根据题意就是要得到我们二叉树的前序遍历，首先我们创建一个链表来接收前序遍历的值，如果二叉树为空直接返回，不为空就创建一个栈，和两个节点，cur指向root,tap指向空。

然后我们要利用循环得到前序遍历的结果，我们知道前序遍历的顺序是：根左右，因此我们要先去左树，我们从根结点开始入栈，每入一个节点就在链表中添加一个结点值，并往下向左结点走，如果此时我们的左节点为空了，我们就弹出此时的栈顶元素，即此时左节点的根节点，给tap，在让cur指向tap的右结点，如果此时的右结点不为空，就放入到栈和链表中，并继续走左节点，为空就重复上面的操作，但如果此时的右节点为空，就代表新的cur为空，但是此时栈不为空，我们还是进入循环，而这样的操作就返回到了我们的上一层。于是在不断循环下就得到了我们的前序遍历

完整代码 

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        if(root == null){
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode tap = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
               stack.push(cur);
              ans.add(cur.val);
               cur = cur.left;
            }
           tap = stack.pop();
           cur = tap.right;
        }
       return ans;
    }
}

6、二叉树的中序遍历

习题链接https://leetcode.cn/problems/binary-tree-inorder-traversal/description/https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

描述：

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

解题思路

他的思路跟上面是一样的，此时他是要我们得到是中序遍历的结果，而中遍历的顺序是：左根右，因此我们放入栈的时机是左子树走完了才能放入到链表中，因此我们只需要将上面放入链表的代码，放到左子树为空的时候，并且我们要存放的第一个元素应该是我们此时左子树的最后一个结点，所以我们要放入的是此时的栈顶元素。

完整代码 

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        if(root == null){
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode tap = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            tap = stack.pop();
            ans.add(tap.val);
            cur = tap.right;
        }
        return ans;
    }
}

7、二叉树的后序遍历

习题链接https://leetcode.cn/problems/binary-tree-postorder-traversal/description/https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

描述：

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

解题思路

他的思路跟上面还是一样的，此时他是要我们得到是后序遍历的结果，而后遍历的顺序是：左右根，因此我们放入栈的时机是左子树走完了并且右子树也走完才能放入到链表中。

因此我们需要在我们的左子树为空时利用if语句判断，他的右子树是否为空，如果为空就出栈，并将原来的栈顶元素放入链表中，如果不为空就让cur等于此时栈顶元素的右边结点（注意：这里tap的赋值，不能用pop,而是用peek，因为，如果此时左子树为空的，但是右子树不为空，我们还需要继续往栈中入栈，因为后序遍历的顺序根左右根，我们需要将左子树和右子树走完才能打印根节点）

但是我们需要注意，在这样的情况下我们会陷入死循环，不断打印右子树最后的值，我们先来看下面

此时cur为空，tap等于结点7，tap.right 为空，此时我们就出栈并在链表中放入结点7，当时我们走完后栈不为空，再次进入循环此时cur为空，tap就等于结点5，但是结点5的右边为结点7不为空，cur 此时就等于结点7，然后cur此时就不为空，结点7，再次入栈，在这样的情况下我们发现我们会不停的打印结点7，陷入了死循环。

因此这时我们需要定义一个变量prev，让他存储弹出的结点，并在if判断中进行判断，如果此时的tap右边不为空但是他的右边等于我们弹出的元素我们就让他进入循环弹出此时栈顶元素，并放入链表中

例如：根据上面的图弹出7后，再次进入循环tap=5，此时tap.right为7不为空，但是tap.right为7等于我们的prev即弹出过的元素，就不往下走直接进入循环弹出结点5，这样就防止了死循环

完整代码 

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        if(root == null){
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode tap = null;
        TreeNode prev = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            tap = stack.peek();
            if(tap.right == null || tap.right == prev){
                stack.pop();
                ans.add(tap.val);
                prev = tap;
            }else{
                cur = tap.right;
            }
        } 
        return ans;
    }
}

好了，今天的分享就到这里了，还请大家多多关注，我们下一篇见！