二叉树终章

文章目录

二叉树终章

本文 还是 为 二叉树 的 练习题

来看第一个题

二叉树的最近公共祖先

附上代码

classSolution{publicTreeNodelowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){if(root ==null){returnnull;}if(p == root || q == root){return root;}TreeNode leftTree =lowestCommonAncestor(root.left,p,q);TreeNode rightTree =lowestCommonAncestor(root.right,p,q);if(leftTree ==null){return rightTree;}if(rightTree ==null){return leftTree;}return root;}}

逻辑清晰些

classSolution{publicTreeNodelowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){if(root ==null)returnnull;if(p == root || q == root)return root;TreeNode leftTree =lowestCommonAncestor(root.left,p,q);TreeNode rightTree =lowestCommonAncestor(root.right,p,q);if(leftTree !=null&& rightTree !=null){return root;}elseif(leftTree !=null){// 左树不为空，右数为空，return leftTree;}else{// 右树不为空，左数为空return rightTree;}}}

完成了 以上 那么 我们接下来 在来一种方法

接下来就 与 求 链表 交点一个思路 没啥难度，那么 你能自己完成吗？？？

附上代码

classSolution{publicbooleangetPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){if(root ==null|| node ==null){returnfalse;}
        stack.push(root);if(root == node){returntrue;}boolean flg =getPath(root.left,node,stack);if(flg){returntrue;}
        flg =getPath(root.right,node,stack);if(flg){returntrue;}
        stack.pop();returnfalse;}publicTreeNodelowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){if(root ==null){returnnull;}Stack<TreeNode> stack1 =newStack<>();Stack<TreeNode> stack2 =newStack<>();getPath(root,p,stack1);getPath(root,q,stack2);int size1 = stack1.size();int size2 = stack2.size();if(size1 > size2){int ret = size1 - size2;while(ret !=0){
                stack1.pop();
                ret--;}while(!stack1.isEmpty()&&!stack2.isEmpty()){if(stack1.peek()== stack2.peek()){return stack1.peek();}
                    stack1.pop();
                    stack2.pop();}}else{int ret = size2 - size1;while(ret !=0){
                stack2.pop();
                ret--;}while(!stack1.isEmpty()&&!stack2.isEmpty()){if(stack1.peek()== stack2.peek()){return stack1.peek();}
                    stack1.pop();
                    stack2.pop();}}returnnull;}}

二叉搜索树与双向链表

接下来我们 来看这道题

附上代码

publicclassSolution{TreeNode prev =null;publicvoidinorder(TreeNode root){if(root ==null){return;}inorder(root.left);
        root.left = prev;//这里如果 不加条件 root != null // 就会出现 空指针异常if(prev !=null){
            prev.right = root;}
         prev = root;inorder(root.right);}publicTreeNodeConvert(TreeNode root){// 创建完 了 双向链表那么就要 去找到 head 结点了if(root ==null){returnnull;}inorder(root);TreeNode head = root;while(head.left !=null){
            head = head.left;}return head;}}

从前序与中序遍历序列构造二叉树

附上代码

classSolution{publicint preIndex =0;publicTreeNodecreateTreeBypandI(int[]preorder,int[]inorder,int inbegin,int inend){if(inbegin > inend){returnnull;}int ret = preorder[preIndex];TreeNode root =newTreeNode(ret);int rootIndex =findIndexOfI(inorder,inbegin,inend,ret);if(rootIndex ==-1){returnnull;}
       preIndex++;
       root.left =createTreeBypandI(preorder,inorder,inbegin,rootIndex -1);
       root.right =createTreeBypandI(preorder,inorder,rootIndex+1,inend);return root;}publicintfindIndexOfI(int[]inorder,int inbegin,int inend,int key){for(int i = inbegin;i<= inend;i++){if(inorder[i]== key){return i;}}return-1;}publicTreeNodebuildTree(int[] preorder,int[] inorder){if(preorder ==null|| inorder ==null){returnnull;}returncreateTreeBypandI(preorder,inorder,0,inorder.length-1);}}

从中序与后序遍历序列构造二叉树

附上代码

classSolution{publicstaticint posIndex =0;publicTreeNodec(int[]inorder,int[]postorder,int inbegin ,int inend){if(inbegin > inend){returnnull;}int ret = postorder[posIndex];TreeNode root =newTreeNode(ret);int rootIndex =findIndex(inorder,inbegin,inend,ret);if(rootIndex ==-1){returnnull;}
        posIndex--;// 注意 后序遍历 是 左子树 --> 右子树 --> 根随// 随意 这里需要先创建 右子树
        root.right =c(inorder,postorder,rootIndex +1,inend);
        root.left =c(inorder,postorder,inbegin,rootIndex-1);return root;}publicintfindIndex(int[] inorder,int inbegin,int inend,int key){for(int i = inbegin;i <= inend; i++){if(inorder[i]== key){return i;}}return-1;}publicTreeNodebuildTree(int[] inorder,int[] postorder){if(inorder ==null|| postorder ==null){returnnull;}// 初始化全局变量 preIndex
            posIndex = postorder.length-1;// c 创建 二叉树returnc(inorder,postorder,0,inorder.length -1);}}

根据二叉树创建字符串

附上代码

classSolution{publicvoidtrreeToString(TreeNode root,StringBuilder sb){if(root ==null){return;}
        sb.append(root.val);if(root.left !=null){// 根据刚刚分析  只要 root.left != null 我们 就需要添加一个 （
            sb.append("(");trreeToString(root.left,sb);
            sb.append(")");}else{// root.left == nullif(root.right ==null){// 这里我们 刚刚分析，如果 root.right == null 说明此时 需要添加一个 ） ，//我们可以放到递归返回的地方添加return;}else{// root.right != null 这里我们就需要 添加一个()
                sb.append("()");}}//左树走完 来 右树if(root.right !=null){
            sb.append("(");trreeToString(root.right,sb);
            sb.append(")");}else{//root.right == null// 此时 树为空直接 return 出去即可return;}}publicStringtree2str(TreeNode root){if(root ==null){returnnull;}StringBuilder sb =newStringBuilder();trreeToString(root,sb);return sb.toString();}}

二叉树的前序遍历非递归

附上代码

classSolution{publicList<Integer>preorderTraversal(TreeNode root){List<Integer> list =newArrayList<>();Stack<TreeNode> stack =newStack<>();TreeNode cur = root;while(cur !=null||!stack.isEmpty()){while(cur !=null){
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;}TreeNode top = stack.pop();
            cur = top.right;}return list;}}

二叉树的中序遍历非递归

附上代码

classSolution{publicList<Integer>inorderTraversal(TreeNode root){List<Integer> ret =newArrayList<>();Stack<TreeNode> stack =newStack<>();TreeNode cur = root;while(cur !=null||!stack.isEmpty()){while(cur !=null){
                stack.push(cur);
                cur = cur.left;}TreeNode top = stack.pop();// System.out.println(top.val+" ");
            ret.add(top.val);
            cur = top.right;}return ret;}}

二叉树的后序遍历非递归

附上代码

classSolution{publicList<Integer>postorderTraversal(TreeNode root){List<Integer> list =newArrayList<>();Stack<TreeNode> stack =newStack<>();if(root ==null){return list;}TreeNode cur = root;TreeNode prev =null;while(cur !=null||!stack.isEmpty()){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;}}

二叉树完结。