二叉树

重建二叉树

1. 二叉树的遍历
   1. 前序:根节点->左子树->右子树
   2. 中序:左子树->根节点->右子树
   3. 后序:左子树->右子树->根节点

二叉树中和为某一值的路径值

题目在解答时在方法外定义了一个容器来装载每一次的遍历结果，然后最后进行返回。

public class Solution {
    private ArrayList<ArrayList<Integer>> listall = new ArrayList<>();
    private ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if (root == null)
            return listall;
        target -= root.val;
        list.add(root.val);
        if(target == 0 && root.left == null && root.right == null)
        {
            listall.add(new ArrayList<Integer>(list));            
        }
        FindPath(root.left,target);
        FindPath(root.right,target);
        list.remove(list.size()-1);
        return listall;
    }
}

或者选择在每一次递归的规程中将该ArrayList<ArrayList<integer>>进行传递。</integer>

public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> arr=new ArrayList<ArrayList<Integer>>();
        if(root==null)
            return arr;
        ArrayList<Integer> a1=new ArrayList<Integer>();
        int sum=0;
        pa(root,target,arr,a1,sum);
        return arr;
    }
    public void pa(TreeNode root,int target,ArrayList<ArrayList<Integer>> arr, ArrayList<Integer> a1,int sum){
        if(root==null)
            return ;
        sum+=root.val;

        if(root.left==null&&root.right==null){
            if(sum==target)
                { a1.add(root.val);
                arr.add(new ArrayList<Integer>(a1));
                a1.remove(a1.size()-1);

            }
          return ;

        }

         a1.add(root.val);
         pa(root.left,target,arr,a1,sum);
        pa(root.right,target,arr,a1,sum);
        a1.remove(a1.size()-1);






    }
}

二叉树的中序遍历

import java.util.Stack;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        Stack<TreeNode> mystack = new Stack<>();
        TreeNode res = null;
        TreeNode pre = null;
        boolean head = true;
        if(pRootOfTree == null)
            return pRootOfTree;
        while(pRootOfTree!=null || !mystack.isEmpty())
        {
            while(pRootOfTree!= null)
            {
                mystack.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            }
            pRootOfTree = mystack.pop();
            if(head == true){
                res = pRootOfTree;
                pre = pRootOfTree;
                head = false;
            }
            else{
                pRootOfTree.left = pre;
                pre.right = pRootOfTree;
                pre = pRootOfTree;
            }
            pRootOfTree = pRootOfTree.right;
        }
        return res;
    }
}