C# use stack to keep current node and preorder traverse


  • 0
    C

    C# use stack to keep current node and do preorder traverse to build tree

       public TreeNode BuildTree(int[] preorder, int[] inorder) {
            if (inorder.Length == 0 || preorder.Length == 0)
            {
                return null;
            }
    
            Stack<TreeNode> st = new Stack<TreeNode>();
            TreeNode root = new TreeNode(preorder[0]);
    
            st.Push(root);
            int j = 0;
            for (int i = 1 ; i < preorder.Length; i++)
            {
                TreeNode cur = st.Peek();
                if (cur.val != inorder[j])
                {
                    cur.left = new TreeNode(preorder[i]);
                    st.Push(cur.left);
                }
                else
                {
                    while(st.Count != 0 && st.Peek().val == inorder[j])
                    {
                        j++;
                        cur = st.Pop();
                    }
                    if(j < preorder.Length)
                    {
                        cur.right = new TreeNode(preorder[i]);
                        st.Push(cur.right);
                    }
                }
            }
    
            return root;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.