二叉树进阶oj题目

二叉树进阶oj题目

• 两个结点的最近公共祖先
• 前序中序（中序后序）还原二叉树

1、两个结点的最近公共祖先（两种方法）

leetcode链接
题目描述：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”如下图所示：

对于这个问题，有两种方法可以解决。
方法一：分类讨论
思考一下，p和q结点相较于最初的根结点root的位置有哪几种情况？

• 1、p和q结点中的一个是root结点
• 2、p和q结点分别在root结点的左右子树中
• 3、p和q结点都在root结点的一颗子树中

对于情况1，p和q结点的最近公共祖先必然为root，直接返回root即可。
对于情况2，p和q的最近公共祖先也为root，直接返回root即可。
对于情况3，我们需要对于root结点的左孩子和右孩子递归调用这个寻找公共祖先的方法，如果两个方法得到的返回值都不为空，返回当前结点即可。否则，返回非空的那个结点。（不存在两个都为空的情况）。以下是代码的呈现：

public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q) {
        if(root==null) return null;
        if(q==root) return q;//找到了结点就返回
        if(p==root) return p;
        TreeNode retleft = lowestCommonAncestor(root.left,p,q);//左孩子递归
        TreeNode retright = lowestCommonAncestor(root.right,p,q);//右孩子递归
        if(retleft!=null&&retright!=null) {
            return root;
        }else if(retleft==null) {
            return retright;
        }else {
            return retleft;
        }
}

方法二：记录路径
实际上，我们只要能够**记录下根节点到p结点和q结点的路径，这两个路径事实上是两个链表，这个问题就可以转化成两个链表相交的问题。**由于二叉树的结点并没有parent引用，无法从下往上将路径贯通，那我们该如何来记录路径呢？**我们使用的思路类似于dfs（深度优先搜索），同时使用栈这种数据结构，一条条路径去尝试。**对于非叶子结点，将左孩子结点入栈，不断递归判断是否为p或q，是p或q结点就返回，否则直到叶子节点开始返回，将不在所求路径上的结点出栈，并将右孩子结点放入。在将结点反复地出入栈后，最后栈里留下的就是root到p或q结点的路径。（p和q结点的路径需要分别存放在两个栈中）。
代码如下：

 public boolean getPath(TreeNode root, TreeNode node,
                           Stack<TreeNode> stack) {
        if(root == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean flgLeft = getPath(root.left,node,stack);
        if(flgLeft) {
            return true;
        }
        boolean flgRight = getPath(root.right,node,stack);
        if(flgRight) {
            return true;
        }
        stack.pop();
        return false;
    }

接下来，就是处理链表相交结点的问题，解决步骤：
1、计算两个栈（链表）的大小之差diff（大-小）
2、将较大的栈（链表）中diff个元素出栈（尾删）
3、当两个栈（链表）不为空时，遍历比较栈顶（链表头）的元素，相同则直接返回，不同则分别出栈（尾删），重复操作直到相同。

2、前序中序（中序后序）还原二叉树

前序中序：leetcode链接
中序后序：leetcode链接
在讲解这道题目前，我们要对二叉树的前序、中序和后序遍历有一个更深刻的了解。
我们先来对前序和中序遍历还原二叉树的过程做一个模拟。比如说我们有一个前序和中序的二叉树遍历序列：
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
我们要做的就是从前到后遍历preorder，而inorder是用来确定左子树和右子树是由哪些部分构成的。我们来模拟一下这个过程：
1、preorder中第一个结点3，在inorder中3在下标1的位置，3的左边就是左子树，右边就是右子树
2、preorder中第二个结点9，在inorder中9在下标0的位置，9的左边没有数，左树为空，右边本来应该是3，但是3已经访问过了，所以9的右树也为空。

以此类推，我们就可以还原出整棵树。我们在还原过程中要用到四个参数，preorder序列，inorder序列，以及inBegin，inEnd来判断是否这个结点的子树是否还原完成，**初始值分别赋为0和preorder.length-1,**可以通过构建一个函数buildChildTree方法来实现。

  public int preIndex；//定义为静态成员变量，防止受到递归的影响
  public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,preorder.length-1);
  }

buildTreeChild方法实现步骤：
1、创建结点

   TreeNode root = new TreeNode(preorder[preIndex]);

2、中序遍历中找到当前结点下标

   int rootIndex = findRooIndex(inorder,inBegin,inEnd,preorder[preIndex]);
   preIndex++；

   public int findRooIndex(int[] inoder,int inBegin,int inEnd,int key) {
        for(int i=inBegin;i<=inEnd;i++) {
            if(inoder[i]==key) {
                return i;
            }
        }
        return -1;
    }

3、分别创建左右子树

   root.left = buildTreeChild(preorder,inorder,inBegin,rootIndex-1);
   root.right =buildTreeChild(preorder,inorder,rootIndex+1,inEnd);

4、判断条件：inBegin>inEnd，子树构建完毕，返回null
以结点9为例，root.left调用buildTreeChild方法后，这个方法内部，inBegin的值为0，inEnd的值为-1，左树为null，root.right调用buildTreeChild方法后，这个方法内部inBegin为1，inEnd为preorder.length-1，因为查找不到9，rootIndex返回-1。
下面是完整的代码呈现:

class Solution {
    public int preIndex;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,preorder.length-1);
    }
    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inBegin,int inEnd) {
        if(inBegin>inEnd) {
            return null;
        }
        //1、创建结点
        TreeNode root = new TreeNode(preorder[preIndex]);
        //2、中序遍历中找到当前结点下标
        int rootIndex = findRooIndex(inorder,inBegin,inEnd,preorder[preIndex]);
        preIndex++;
        //3、分别创建左右子树
        root.left = buildTreeChild(preorder,inorder,inBegin,rootIndex-1);
        root.right =buildTreeChild(preorder,inorder,rootIndex+1,inEnd);
        return root; 
    }
    public int findRooIndex(int[] inoder,int inBegin,int inEnd,int key) {
        for(int i=inBegin;i<=inEnd;i++) {
            if(inoder[i]==key) {
                return i;
            }
        }
        return -1;
    }
}

而对于后序中序还原二叉树，我们也可以按照这种思路模拟实现。唯一需要注意的是我们要从后向前遍历posorder这个序列，同时要先创建右子树，再创建左子树，这样才能符合二叉树后序遍历的顺序。下面直接呈现代码：

class Solution {
    public int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = inorder.length-1;
        return buildTreeChild(postorder,inorder,0,inorder.length-1);
    }
    public TreeNode buildTreeChild(int[] postorder,int[] inorder,int inBegin,int inEnd) {
        if(inBegin>inEnd) {
            return null;
        }
        //1、创建结点
        TreeNode root = new TreeNode(postorder[postIndex]);
        //2、中序遍历中找到当前结点下标
        int rootIndex = findRooIndex(inorder,inBegin,inEnd,postorder[postIndex]);
        postIndex--;
        //3、分别创建右左子树
        root.right =buildTreeChild(postorder,inorder,rootIndex+1,inEnd);
        root.left = buildTreeChild(postorder,inorder,inBegin,rootIndex-1);
        return root; 
    }
    public int findRooIndex(int[] inoder,int inBegin,int inEnd,int key) {
        for(int i=inBegin;i<=inEnd;i++) {
            if(inoder[i]==key) {
                return i;
            }
        }
        return -1;
    }
}