二叉树day13

108. 将有序数组转换为二叉搜索树

递归

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }
    private TreeNode build(int[] nums, int s, int e) {
        //递归终止条件
        if (s > e) return null;
        else if (s == e) return new TreeNode(nums[s]);
        //根节点
        int m = (s + e) / 2;
        TreeNode root = new TreeNode(nums[m]);
        //构造子树
        root.left = build(nums, s, m - 1);
        root.right = build(nums, m + 1, e);
        return root;
    }
}

迭代

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        int len = nums.length;
        if (len == 0) return null;
        Deque stack = new LinkedList<>();
        int s = 0, e = len - 1, m = (s + e) / 2;
        TreeNode root = new TreeNode(nums[m]);
        //将当前构造树的根节点 数组终点 中点 起点压入栈中，注意入栈和出栈的顺序
        if (e > s) {
            stack.push(root);
            stack.push(e);
            stack.push(m);
            stack.push(s);
        }
        while (!stack.isEmpty()) {
            s = ((Integer) stack.pop()).intValue();
            m = ((Integer) stack.pop()).intValue();
            e = ((Integer) stack.pop()).intValue();
            TreeNode cur = (TreeNode) stack.pop();

            //构造左子树
            if (m - 1 < s) cur.left = null;
            else if(m - 1 == s) cur.left = new TreeNode(nums[s]);
            else {
                int lm = (s + m - 1) / 2;
                cur.left = new TreeNode(nums[lm]);
                stack.push(cur.left);
                stack.push(m - 1);
                stack.push(lm);
                stack.push(s);
            }

            //构造右子树
            if (e < m + 1) cur.right = null;
            else if(e == m + 1) cur.right = new TreeNode(nums[m + 1]);
            else {
                int rm = (m + 1 + e) / 2;
                cur.right = new TreeNode(nums[rm]);
                stack.push(cur.right);
                stack.push(e);
                stack.push(rm);
                stack.push(m + 1);
            }
        }
        return root;

    }
}



538. 把二叉搜索树转换为累加树


直接右中左遍历 从大到小 定义pre记录前面遍历的一个结点


递归


class Solution {
    private TreeNode pre = null;
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;
        //右
        if (root.right != null) convertBST(root.right);

        if (pre != null) root.val += pre.val;
        pre = root;

        //左
        if (root.left != null) convertBST(root.left);
        return root;
    }
}


迭代


//迭代 右中左
class Solution {
    public TreeNode convertBST(TreeNode root) {
        Deque stack = new LinkedList<>();
        stack.push(root);
        TreeNode pre = null;
        while (!stack.isEmpty()) {
            TreeNode cur = stack.peek();
            // if (cur == null) System.out.print(cur + " hhhh:");
            // else System.out.print(cur.val + " hhhh:");      
            while (cur != null) {
                //System.out.print(cur.val + " ");
                stack.push(cur.right);
                cur = cur.right;
            }
            //空指针退栈
            stack.pop();
            //如果cur == null 即上一个操作的结点左子树为null 此时操作的便是上一个操作结点的父结点
            if (!stack.isEmpty()) {
                cur = stack.pop();
                //System.out.println("cz: "+cur.val);
                if (pre != null) cur.val += pre.val;
                pre = cur;
                stack.push(cur.left);
            }
        }
        return root;

    }
}




二叉树先告一段落啦，接下来开始刷回溯。


参考：programmercarl.com

						  
					  
						
							


						

							
							
			算法							
						



						

						
						


						

						
					
					

					
					

						
相关

						

				
						
			

																
								

										
如何实现LRU（最近最少使用）缓存淘汰算法？

									
									

								 

        

								

							
							

																
								

										
2021.11.16（各排序算法对比）

									
									

								 

        

								

							
							

																
								

										
react dom移动算法

									
									

								 

        

								

							
							

																
								

										
算法第四章上机实验报告

									
									

								 

        

								

							
							

																
								

										
算法第二章实践报告

									
									

								 

        

								

							
							

																
								

										
【莫队算法】

									
									

								 

        

								

							
							

																
								

										
算法第四章实践报告

									
									

								 

        

								

							
							

																
								

										
关于tarjan算法的一些整理

									
									

								 

        

								

							
							

																
								

										
【基础】排序算法学习笔记

									
									

								 

        

								

							
							

																
								

										
常用的排序算法介绍和在JAVA的实现（一）

									
									

								 

        

								

							
							

																
								

										
数据结构与算法之PHP查找算法（哈希查找）

									
									

								 

        

								

							
							

																
								

										
数据结构与算法之PHP查找算法（二分查找）

									
									

								 

        

								

							
							
            
            
            
                                    
           
  			
						

					

					
				

				

														
					
					

					
									

					
									   
标签

										

										
    
										

									

										
										

									

					

					
				


			
		
		
		
			


						





	

	
一品网 冀ICP备14022925号-6